题意: 个数分为两组,然后开始从头遍历,每秒向后+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