[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);
}
}
}

加入对话

9条评论

留下评论

您的电子邮箱地址不会被公开。