糖糖别胡说,我真的不是签到题目

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;
}
原文地址:https://www.cnblogs.com/xcfxcf/p/12922814.html