[ZOJ3385 Hanami Party]【贪心】【栈】★★

【题目大意】
一开始主角有一个能力值L，然后有n天，每天他可以执行下列两个操作中的其中一个：
1：自身能力值+1
2：制造与自己能力值相等个单位的食物。
另外，每天食物都会被饿鬼吃掉一些，但是主角又不能惹怒这个饿鬼。
求在不惹怒这个饿鬼的情况下，最后剩余食物最多能是多少？
如果必须惹怒，那么输出Myon。
【算法分析】
下面的 1 2分别表示操作1和操作2。
本题可以利用贪心来解决。
我们的策略应该是尽量升级，然后必须造食物才造。就是升级的尽量前推。
因为如果出现 2,1这种情况，而1和2可以交换而使得没有出现饿鬼被惹怒的情况，那么显然交换以后能造多一个单位的食物。所以升级是应该被尽量前推的。
可以发现其实我们是将这个操作分组，分成这样的数段：（1,2,2…2）,（1,2,2…..2）,（1,2,2….2)
（一开始在0天时我们看做操作1）
现在我们只关心操作1的划分。
为了实现我们的策略，那么我们对于前i天，都求出最多所能进行操作1多少次。
这可以用一个栈来解决。
这个栈里面存的是每次操作1所发生的时间。
然后每次把今天是操作1放进栈内。
如果栈尾的元素到今天不能满足饿鬼的需求，那么退栈，
这样我们维护的一个栈是所有升级操作都尽量前推好的了。并且到了第i天所能升级最多次的。
当然，如果栈里连第0天那个虚拟的升级都被退了，那么就无解了。
、
、
、
、
现在可能还有一些疑问，那就是升级多了固然会把饿鬼惹怒，但是有时候升级少了我们也会把饿鬼惹怒的。
比如说一开始能力值为0，然后你造食物多少天也没用。这样还是会惹怒饿鬼。
就是说，不能保证退栈以后依然是可行解。
、
、
、
、
现在我们再来看看一个东西。
假如说，我们退栈导致某个地方饿鬼不爽了。
那么我们从这个饿鬼不爽的地方分开来看。
假设饿鬼不爽这一天为j。
对于我们现在的第i天来讲，我们在第j天时，退栈前，能力强，剩余的食物也多。
（因为栈的大小代表升级的次数，并且原来饿鬼在第j天时爽的，退栈以后不爽，可以说明剩余食物变少了）
那么既然这样，如果会使得该解退栈后成为非可行解的，对于第i天来讲，是有害无利。
但是退栈的条件是升级这么多不行了。
所以，其实如果走出了这一步退栈，实际就是无解了。
我们会一直退到栈空为止。判为无解。
、
、
、
、
做完了第n天以后，我们还要把所有元素退栈，因为到了后面可能造食物更为划算。
然后这里退栈造成的非可行解问题，我们上面已经说明，如果是造成了非可行解，那么答案只会更差。
而我们取的最优值，所以一起判断也没关系。
然后，我们就得出了这个O(n)的贪心算法。
【其它】
泪流满面，3Y。原因是这个ZOJ的int64。。。居然这么标准，和NOI一样用long long+%lld。。。一开始就搞%I64d。搞挂了。
其实一开始我是看了一下月赛的Ranklist，发现最后一题好像每个人都A了。。。
然后想去切一下准备NOIP。。。
切了好一会儿终于切掉该题，感觉怎么现在的人都这么强T_T，这种题成为众人秒杀类题目。
颓然发现，由于题目过多，他那个Ranklist在我的浏览器下，下面还有横条。原来我看到众人秒杀的是倒数第二题。。。而最后一题只有navi大神AC。。。
【CODE】
#include #include #include #include using namespace std;
typedef long long lld;
const lld N=100005;
lld n,init_L,Qt;
lld a[N],Q[N],Rest_Food[N];
lld Sum[N];

int main(){
while (scanf("%lld%lld",&n,&init_L)!=EOF){
lld i,j,ans;
for (i=1;i<=n;i++) scanf("%lld",&a[i]);
for (Sum[0]=0,i=1;i<=n;i++) Sum[i]=Sum[i-1]+a[i];
Qt=Rest_Food[0]=Q[0]=0;
for (i=1;i<=n;i++){
Qt++;
Q[Qt]=i;
Rest_Food[Qt]=Rest_Food[Qt-1]+(init_L+Qt-1)*(i-Q[Qt-1]-1)-(Sum[i]-Sum[Q[Qt-1]]);
while (Qt>=0 && Rest_Food[Qt]+(i-Q[Qt])*(init_L+Qt) if (Qt<0) break;
}
if (Qt<0) puts("Myon");
else{
ans=0;
while (Qt>=0){
if (Rest_Food[Qt]+(n-Q[Qt])*(init_L+Qt)-(Sum[n]-Sum[Q[Qt]])>ans)
ans=Rest_Food[Qt]+(n-Q[Qt])*(init_L+Qt)-(Sum[n]-Sum[Q[Qt]]);
Qt–;
}
printf("%lldn",ans);
}
}
}