「RQNOJ166」免费午餐
题目描述
为了增加顾客,Sally的店铺决定提供免费午餐,顿时门庭若市,但是不久Sally的原材料不足了….因此Sally决定公布一项决定:凡是来本店吃免费午餐的,一天吃能吃一次,吃的数量必须比上一次吃的少, 点的必须在上一次后面，且免费午餐将只有N个种类任君选择,为了能吃到最多的免费午餐,你将如何安排每日吃的数量呢?
输入格式第一行一个数N，表示免费午餐的种类（0<=N<=100000)
第二行N个数，表示每个免费午餐的数量（0<=数量<=100000）
输出格式一个数,表示最多能吃多少天
样例输入
5
5 4 3 2 1
样例输入
5
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include<iostream> #include<cstring> using namespace std; int main() { int n; int a[100001],f[100001],ans=0; cin>>n; memset(f,127/3,sizeof(f)); for(int i=n;i>0;i--) { cin>>a[i]; } f[0]=0; for(int i=1;i<=n;i++) for(int j=ans;j>=0;j--) { if(a[i]>f[j]){f[j+1]=min(a[i],f[j+1]);ans=max(ans,j+1);break;} } cout<<ans; return 0; } |
二分排序
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include<iostream> #include<cstring> using namespace std; int n; int a[100001],f[100001],ans=0; int find(int right,int x) { int left=0; int mid=(left+right)/2; while(left<=right) { if(x>f[mid])left=mid+1; else if(x<f[mid])right=mid-1; else return mid; mid=(left+right)/2; } return left; } int main() { cin>>n; memset(f,127,sizeof(f)); for(int i=n;i>0;i--) { cin>>a[i]; } f[0]=0; for(int i=1;i<=n;i++) { int j=find(ans,a[i]); f[j]=min(a[i],f[j]);ans=max(ans,j); } cout<<ans; return 0; } |
Subscribe
计数器 9854368
OI 课件=>
OI 课件=>