https://ac.nowcoder.com/acm/problem/14583
t组测试样例,n个糖糖,发功次数m,已知组号ai和能力值bi;发功时间ci(b1到bci都会加1);
当到了i的时候,判断j能不能被消灭 j < i, 能力值 bj < bi, i和j不属于同一组
从后往前,分别记录两组的最大值(max比当前大,说明可以消灭)
#include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 5e4 + 10; int t,n,m,max0,max1; struct node{ int a,b; }e[maxn]; int c[maxn]; int cnt; signed main() { // freopen("in","r",stdin); ios::sync_with_stdio(0); cin >> t; while(t--){ cin >> n >> m; for(int i = 1; i <= n; i++) cin >> e[i].a >> e[i].b; memset(c,0,sizeof(c)); for(int i = 1; i <= m; i++) { int x; cin >> x; c[x]++; } for(int i = n; i >= 1; i--){ c[i] += c[i + 1]; e[i].b += c[i]; } max0 = max1 = cnt = 0; for(int i = n; i >= 1; i--){ if(!e[i].a){ max0 = max(max0,e[i].b); if(max1 > e[i].b) cnt++; }else{ max1 = max(max1,e[i].b); if(max0 > e[i].b) cnt++; } } cout << n - cnt << endl; } return 0; }