每日一题4月21日 糖糖别胡说 思维+区间修改
糖糖别胡说,我真的不是签到题目
https://ac.nowcoder.com/acm/problem/14583
这道题想了很久,但是自己思路局限性太大了。
题目大意:
比较麻烦,就不解释了。原文贴一下:
从前,有n只萌萌的糖糖,他们分成了两组一起玩游戏。他们会排成一排,第i只糖糖会随机得到一个能力值bi。从第i秒的时候,第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。
请在这里输入引用内容
为了使游戏更加有趣,糖糖的爸爸,娇姐,会发功m次,第i次发功的时间为ci,则在第ci秒结束后,b1,b2,.....,bci都会增加1.
请在这里输入引用内容
现在,娇姐想知道在第n秒后,会有多少只糖糖存活下来。
思路:
这题主要难住我的在发功的地方。一开始想的是,假设不考虑发功,从前往后按照时间枚举每个糖,如果对于当前糖知道前面有多少个糖比他小就直接删掉那部分糖,这样的话我们可以二分查找,但是二分需要数组有序,要O(n)维护有序的话感觉要用到链表了。但是即使用了链表,发功问题我还是解决不掉。
后来考虑用树状数组维护,发功的时候对当前点直接减去发功次数就可以了,但是问题是无法判断前面的点到底被发功了几次。
看了题解。
我看到一个做法是维护两个小顶堆,然后暴力地去删除,然后发功的话就可以用减法减次数来计算。
我以为这样时间上过不了。不过仔细想想好像可以的。
题解的做法是,从后往前维护每个组的最大值,那么我们只考虑当前的点会不会被删除,当前点被删除只可能是后面的点比他大。因此从后往前维护每个组的最大值。
那么发功怎么办呢?可以发现发功每次都是对1 ~ ci的点进行发功,所以其实如果在i ~ j的时间点内发功(i<j)的话,i有可能不会被j消灭,j后面的发功会令i和j一起变化,i前面的发功不会对i和j产生影响。所以实际上,我们只需要判断b[i]+(i之后的发功次数)与b[j]+(j之后的发功次数)的大小关系就好了。
换句话说,我事先把所有点的都发功弄好,然后按照从后往前维护最大值进行判断的方法去做就好了。而先发功其实就是对一些[1,ci]全部+1,这个我们可以用头加加尾减减来解决。
代码:
#include<bits/stdc++.h> using namespace std; int n,m,a[50040],b[50040],c[50050],vis[50005]; int t[2]; int main() { int T; cin>>T; while(T--){ t[0]=t[1]=0; cin>>n>>m; for(int i=1;i<=n;i++){ scanf("%d%d",&a[i],&b[i]); } memset(vis,0,sizeof(vis)); for(int i=1;i<=m;i++){ int x; cin>>x; vis[1]++; vis[x+1]--; } for(int i=1;i<=n;i++)vis[i]+=vis[i-1]; for(int i=1;i<=n;i++)b[i]+=vis[i]; int ans=n; for(int i=n;i>=1;i--){ if(a[i]==0){ if(t[1]>b[i])ans--; t[0]=max(t[0],b[i]); } else { if(t[0]>b[i])ans--; t[1]=max(t[1],b[i]); } } cout<<ans<<endl; } return 0; }