糖糖别胡说,我真的不是签到题目
糖糖别胡说,我真的不是签到题目
http://www.nowcoder.com/questionTerminal/9d5b203a30bc4e7b85f1838d60cf2236
题意:
从前,有n只萌萌的糖糖,他们分成了两组一起玩游戏。他们会排成一排,第i只糖糖会随机得到一个能力值bi。从第i秒的时候,第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。
为了使游戏更加有趣,糖糖的爸爸,娇姐,会发功m次,第i次发功的时间为ci,则在第ci秒结束后,b1,b2,.....,bci都会增加1.
现在,娇姐想知道在第n秒后,会有多少只糖糖存活下来。
思路:差分,模拟。
代码:
#include<bits/stdc++.h> using namespace std; #define ll long long int zu[5000005]; int val[5000005]; int cha[5000005]; int gn[5000005]; int main() { int T; cin >> T; while(T--) { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d%d",&zu[i],&val[i]); for(int i=1;i<=m;i++) scanf("%d",&gn[i]); for(int i=1;i<=n;i++) cha[i]=val[i]-val[i-1]; for(int i=1;i<=m;i++) { cha[1]++; cha[gn[i]+1]--; } for(int i=1;i<=n;i++) val[i]=val[i-1]+cha[i]; int ma[2]; ma[0]=ma[1]=0; int ans=0; for(int i=n;i>0;i--) { if(val[i]>=ma[zu[i]^1]) ans++; if(val[i]>ma[zu[i]]) ma[zu[i]]=val[i]; } printf("%d\n",ans); } return 0; }