题意:
有n只糖糖,排成一排,第i只糖糖能力值bi。从第i秒的时候,第i只糖糖就可以消灭掉所有另外一组排在他前面的糖糖。此外有发功m次,第i次发功的时间为ci,则在第ci秒结束后,b1,b2,.....,bci都会增加1.问第n秒后还剩几只糖糖?
思路:
刚开始想到的是纯暴力,但是根据数据范围必然会t。所以需要进一步优化。
首先我们先思考第i只糖糖存活的条件:假设第i只糖糖在编号为0的队伍里,经过发功之后,排在第i只糖糖的后面的编号为1的糖糖的能力值都小于它,那么他一定会存活。此外,排在i前面的糖糖发功对于彼此之间的能力差值是没有任何影响的(同时加上一个数,差值不变)。所以说,我们只需要从后面往前面扫描,并且维护两队的能力最大值即可。
具体实现方式分为两步:
1>实现发功后能力值加1:根据题干“第i次发功的时间为ci,则在第ci秒结束后,b1,b2,.....,bci都会增加1”,所以说排在前面的糖糖的能力值提升的次数是最多的,故此,我们可以用反向前缀和来存储能力的提升值。
2>实现两个数组的维护:因为糖糖只会消灭排在他之前的糖糖,而排在他后面的即使比他的能力值低也还可以存活,所以我们选择从后面遍历每个糖糖的存活情况,以编号为0的为例,我们需要判断当前该糖糖的能值是否大于等于已经出现过的编号为1的糖糖的能力值的最大值,如果大于,则编号为0的糖糖可以存活,否则死亡。接着我们需要维护编号为0的糖糖的能力值的最大值。
Ac代码:
const int num=5e4+5; struct ndoe { int id,b; }a[num]; int f[num];//存的是反向的前缀和 int main() { int t,m,n; cin>>t; while(t--) { cin>>n>>m; memset(f,0,sizeof(f));//注意要跟新前缀和 int ans=0; for(int i=1;i<=n;i++) cin>>a[i].id>>a[i].b; for(int i=1;i<=m;i++) { int x; cin>>x; f[x]++; }//在第x时刻发功,能力值+1 int m0=-1,m1=-1; for(int i=n;i>=1;i--) { f[i]+=f[i+1];//反向前缀和 a[i].b+=f[i];//最终能力值 if(a[i].id==0) { if(a[i].b>=m1) ans++;//判断是否满足生存条件 m0=max(m0,a[i].b);//最大值的维护 } else { if(a[i].b>=m0) ans++; m1=max(m1,a[i].b); } } cout<<ans<<endl; } return 0; }