题意:
题目有点绕,给出n个人 分别存在两个队里
在第i秒 第i个人会消灭前面能力值比他小 并且是不同队伍的人 同时有m个操作 每次操作一个数x 使得1~x的能力值 +1 求到最后能有多少只活下来
思路:因为到最后一定满足越后面的不同组能力值大于前面的 所以我们直接预处理后缀 一次性更新完所有操作 然后从后向前遍历 维护不同组的最大值 计算有多少会被淘汰 最后答案的话就是 n - cnt
#include <bits/stdc++.h> using namespace std; #define LL long long const int N = 50005; struct node { int id; LL x; }a[N]; LL b[N]; int main() { int t ; scanf("%d",&t); while(t --) { int n,m ; memset(b,0,sizeof(b)); scanf("%d%d",&n,&m); for(int i = 1;i <= n; i ++) scanf("%d%lld",&a[i].id,&a[i].x); int x; for(int i = 1;i <= m;i ++) scanf("%d",&x),b[x] ++ ; for(int i = n;i >= 1;i --) b[i] += b[i + 1] , a[i].x += b[i]; int cnt = 0; LL ma0,ma1; ma0 = ma1 = 0; for(int i = n;i >= 1;i --) { if(a[i].id == 0) { ma0 = max(ma0,a[i].x); if(ma1 > a[i].x) cnt ++ ; } else { ma1 = max(ma1,a[i].x); if(ma0 > a[i].x) cnt ++; } } printf("%d\n",n - cnt); } return 0; }