【糖糖别胡说,我真的不是签到题目】题解
糖糖别胡说,我真的不是签到题目
https://ac.nowcoder.com/acm/problem/14583
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; }