免费午餐 rqnoj167
题目描述
为了增加顾客,Sally的店铺决定提供免费午餐,顿时门庭若市,但是不久Sally的原材料不足了….因此Sally决定公布一项决定:凡是来本店吃免费午餐的,一天吃能吃一次,吃的数量必须比上一次吃的少, 点的必须在上一次后面,且免费午餐将只有N个种类任君选择,为了能吃到最多的免费午餐,你将如何安排每日吃的数量呢?
输入格式
第一行一个数N,表示免费午餐的种类(0<=N<=100000)
第二行N个数,表示每个免费午餐的数量(0<=数量<=100000)
输出格式
一个数,表示最多能吃多少天
样例输入
5
5 4 3 2 1
样例输出
5
这一题很明显是求最长下降子序列,不过数据庞大,需要二分优化,具体怎么优化见下面这篇博客 【最长上升子序列+二分优化】麻烦的聚餐 egroup.pas/c/cpp
还有需要注意的是要跳过为0的情况
C++ Code
/************************** C++ Code http://oijzh.cnblogs.com By jiangzh **************************/ #include<cstdio> #define max(a,b) ((a)>(b)?(a):(b)) int n,a[100010],c[100010]; int main() { freopen("rqn167.in","r",stdin); freopen("rqn167.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); int len=0; for(int i=1;i<=n;i++) { if(a[i]==0)continue; int l=1,r=len,m; while(l<=r) { m=(l+r)>>1; if(c[m]>a[i])l=m+1; else r=m-1; } len=max(len,l); c[l]=a[i]; } printf("%d",len); return 0; }
原文链接: https://www.cnblogs.com/oijzh/archive/2012/10/27/2742728.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/67216
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!