题意:图片说明 个数分为两组,然后开始从头遍历,每秒向后+1位,如果从图片说明 有小于当前的图片说明 时且不是同一组的元素消灭,同时还有个图片说明 次操作就是可以在第图片说明 秒时,可以使图片说明 全部+1,求最后剩余多少个元素
题解:暴力,倒着枚举
图片说明 ,根据这句我们可以先让所有的元素加上相应的数字,如样例所给
图片说明
(最后有点挡住了........)
然后不是说前面大于的全部消灭吗?而且分两组的情况,所以我们可以直接找到0和1两组最后出现的位置,取其元素为图片说明 ,开始从后向前消灭
向前移动的时候如果当前元素大于图片说明,那么更新图片说明,计数.因为如果前面的数全部小于图片说明,那么肯定全部消灭,如果有大于图片说明的,那么这一段的全部消灭,图片说明更新,而且我们只关心结果,所以记录图片说明情况即可,然后要注意分组进行更新和计数
时间复杂度:图片说明

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

const ull N = 1000000007;
const ull mod = 998244353;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1);
const double e = exp(1);

int lazy[50007];
int ans[50007];

bool flag[50007];

int n, m;

int main()
{
    ios::sync_with_stdio(false);
    int t;
    int temp;
    int num;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        memset(lazy, 0, sizeof(lazy));
        memset(ans, 0, sizeof(ans));
        memset(flag, 0, sizeof(flag));
        num = 0;
        for (int i = 1; i <= n; ++i)
        {
            cin >> temp >> ans[i];
            if (temp)
            {
                flag[i] = true;
            }
        }
        for (int i = 0; i < m; ++i)
        {
            cin >> temp;
            ++lazy[temp];
        }
        int max1 = -1;
        int max2 = -1;
        for (int i = n; i > 0; --i)
        {
            lazy[i] += lazy[i + 1];
            ans[i] += lazy[i];
        }
        for (int i = n; i > 0; --i)
        {
            if (flag[i])
            {
                if (ans[i] > max2)
                {
                    max2 = ans[i];
                }
                if (ans[i] >= max1)
                {
                    num++;
                }
            }
            else
            {
                if (ans[i] > max1)
                {
                    max1 = ans[i];
                }
                if (ans[i] >= max2)
                {
                    ++num;
                }
            }
        }
        cout << num << endl;
    }
    return 0;
}
//code:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43075296