题意:
有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;
}

京公网安备 11010502036488号