【糖糖别胡说，我真的不是签到题目】题解

1.前置知识

差分

2.题意

现有n个人，分为两队。他们从第一个开始，消灭所有编号与战力值均比他小的敌人。且有m次操作会在第个人操作后将前个人的战力值加1.求最后剩下多少人。

3.解法

这道题模拟过于麻烦，但是由于它特殊的顺序，使得一个人后面有敌人战斗值大于它，它就一定会被消灭，不会出现敌人先被消灭了的情况。那么我们就不用管顺序，直接由后往前，找出最大战斗力来比较就行了。而m次操作也是从前往后按照顺序进行的，也不用管顺序。只需要处理出最终的无战斗状态，再遍历就行了。

4.时间复杂度

5.代码

#include<stdio.h>
#include<algorithm>
using namespace std;
int T;
int n, m;
int a[50005], b[50005], ch[50005];
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        int max0 = -1e9, max1 = -1e9,ans = 0;
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d %d", &a[i], &b[i]);
            if (i == 1)ch[i] = b[i];
            else ch[i] = b[i] - b[i - 1];
        }
        for (int i = 1; i <= m; i++)
        {
            int x;
            scanf("%d", &x);
            ch[1]++;
            ch[x + 1]--;
        }
        for (int i = 1, tot = 0; i <= n; i++)
        {
            tot += ch[i];
            b[i] = tot;
        }
        for (int i = n; i >= 1; i--)
        {
            if (a[i] == 0)
            {
                max0 = max(max0, b[i]);
                if(b[i] < max1)ans++;
            }
            else
            {
                max1 = max(max1, b[i]);
                if (b[i] < max0)ans++;
            }
        }
        printf("%d\n", n - ans);
    }
    return 0;
}