题目
题目描述:
从前，有 n 只萌萌的糖糖，他们分成了两组一起玩游戏。他们会排成一排，第 i 只糖糖会随机得到一个能力值
b
i
b_i
bi 。从第 i 秒的时候，第 i 只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。
为了使游戏更加有趣，糖糖的爸爸，娇姐，会发功 m 次，第i次发功的时间为
c
i
c_i
ci，则在第
c
i
c_i
ci 秒结束后，
b
1
,
b
2
,
.
.
.
.
.
,
b
c
i
b_1,b_2,.....,b_{ci}
b1,b2,.....,bci 都会增加 1.
现在，娇姐想知道在第 n 秒后，会有多少只糖糖存活下来。
输入描述:
第一行只有一个整数 T（T < 6），表示测试数据的组数。
第二行有两个整数n,m。表示糖糖的个数以及娇姐发功的次数。
（
1
≤
n
≤
50000
,
1
≤
m
≤
1000000
）
（1 \leq n \leq 50000,1 \leq m \leq 1000000）
（1≤n≤50000,1≤m≤1000000）
第三行到 n+2 行,每行有两个整数
a
i
,
b
i
a_i,b_i
ai,bi，表示第 i 只糖糖属于哪一组以及他的能力值。
（
0
≤
a
i
≤
1
,
1
≤
b
i
≤
1000000
）
（0 \leq a_i \leq 1,1 \leq b_i \leq1000000）
（0≤ai≤1,1≤bi≤1000000）
第 n+3 行到第 n+m+2 行，每行有一个整数
c
i
c_i
ci，表示GTW第i次发功的时间。
(
1
≤
c
i
≤
n
)
(1 \leq c_i \leq n)
(1≤ci≤n)
输出描述:
总共 T 行，第 i 行表示第 i 组数据中，糖糖存活的个数。
样例1
输入
1
4 3
0 3
1 2
0 3
1 1
1
3
4
输出
3
提交链接
https://ac.nowcoder.com/acm/problem/14583
解析
最开始想的，外层循环从 1 到 n 枚举每一个糖糖，碰到发功的时刻 i，对于小于 i 的糖糖战斗力++，时间复杂度
n
2
n^2
n2，超时。
优化：
对于每一个发功的时刻，其前面的糖糖的战斗力都要加 1，可以前缀和维护第 i 秒时一共发功了多少次。
假设：j<i
编号为j的糖糖的战斗力增加了sum[i]-sum[j-1]
编号为i的糖糖的战斗力增加了sum[i]-sum[i-1]
若 j 位置的糖糖被i位置的糖糖消去的条件是：
j<i && group[j]!=group[i] && fight[j]<fight[i]
fight[j]=fight[j]+sum[i]-sum[j-1]
fight[i]=fight[i]+sum[i]-sum[i-1]
fight[j]<fight[i]可以转化为：fight[j]-sum[j-1]<fight[i]-sum[i-1]
细节条件：所有的糖糖要么是0组的，要么是1组的。
s[0]，s[1]分别记录所在组的最大的fight[i]-sum[i-1]
倒着扫描，更新最大值
int s[2];
s[0]=s[1]=-2e7; //初始化为最小值
int res=n;
for(int i=n; i>=1; i--)
{
if(fight[i]<s[group[i]^1])///group[i]^1记录不同组，因为是倒序的，s[group[i]^1]记录的是比此时的i大的战斗力
res--;
s[group[i]]=max(s[group[i]],fight[i]);
}
完整代码：
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5*1e4+10;
int group[N];
int fight[N];
int sum[N];
int n,m;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
{
scanf("%d%d",&group[i],&fight[i]);
sum[i]=0;
}
while(m--)
{
int x;
scanf("%d",&x);
sum[x]+=1;
}
for(int i=1; i<=n; i++)
{
sum[i]+=sum[i-1];///前缀和 第i秒时一共加了sum[i]次
fight[i]-=sum[i-1];
}
int s[2];
s[0]=s[1]=-2e7;///初值一定要大
int res=n;
for(int i=n; i>=1; i--)
{
if(fight[i]<s[group[i]^1])
res--;
s[group[i]]=max(s[group[i]],fight[i]);
}
printf("%d\n",res);
}
return 0;
}
