糖糖别胡说，我真的不是签到题目 题号：NC14583 链接：https://ac.nowcoder.com/acm/problem/14583 来源：牛客网

思路：

  1. 因为糖爸发功，前Ci的人都会强化，假设糖爸每次发功，是对所有的人强化，而战力是采用大小比较，那么他的发功跟不发功是一样，毫无影响。题意的每次发功，在Ci秒之后的所有发功，对排在Ci之前的糖果大战结果毫无影响。可以认为把Ci秒之后的所有发功，都提前在Ci秒结束之后立即发功，用立即发功的战力比较，对最终结果也是毫无影响。当Ci的值为0，也就是说，题意可以转化为：在大战之前，弹爸立即发所有的功（发功效果不变，发功效果是指对Ci之前的糖果进行强化的效果），然后开始糖糖大战，最终结果也是不会发生改变。

  2. 在已知的不变固定战力的情况下，计算糖糖的存活数量带来了方便。假设不考虑队伍的情况，最终战况必然是战力处于非严格降序排序。问题转化求一个非严格降序序列，当然，求一个非严格降序序列是较为艰难的，因为不知道后面有没有比当前的值要大，如果大了，那么就不能选择当前的值，显然复杂度为O（n^2）。然而，求一个非严格升序序列却是更为简单，只要不断选择最大值即可，显然复杂度为O(n)，所以从后往前遍历改变复杂度. 考虑到队伍的情况，实际上只是做了比较限制的而已。

另外需要说明一些点：

在Ci秒之后发功，可能发多次，输入的m个发功值Ci并不是升序的，需要使用桶排序。糖糖被消灭了之前，也可能消灭其他糖糖。

附代码：

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
#define MAX(x,y) ((x)>(y)?(x):(y))

using namespace std;
unsigned short fagong[51000];
int b[51000];
unsigned short type[51000];
int strengthenB[51000];
int main() {
	int t;
	cin >> t;

	while (t--) {
		int n, m,ci;
		cin >> n >> m;
		memset(fagong, 0, sizeof(fagong));
		memset(strengthenB, 0, sizeof(strengthenB));
		for (int i = 1; i <= n; i++) {
			cin >> type[i] >> b[i];
		}
		for (int i = 0; i < m; i++) {
			cin >> ci;
			fagong[ci]++;
		}
		// 假设全部存活，求出糖爸强化他们的战力的结果
		for (int i = n; i > 0; i--) {
			strengthenB[i] = strengthenB[i+1] + fagong[i];
			b[i] += strengthenB[i];
		}
		//for (int i = 1; i <=n; i++) {
			//cout << "I: 第" << i << "糖糖战力 " << b[i] << endl;
		//}
		// 因为之前假设全部存活，现在开始让他们互相消灭大战
		// 需要从后往前遍历
		int maxB[2] = {-1,-1};
		int ret = 0;
		for (int i = n; i > 0; i--) {
			if (b[i] >= maxB[!type[i]]) {
				// 最终第i个糖糖存活(因为没有强天敌，注：它的天敌是指排在他之后的不同组的糖糖)
				ret++;
				//cout << "I: 第" << i << "糖糖存活 " <<b[i]<< endl;
			}
			maxB[type[i]] = MAX(maxB[type[i]], b[i]);
		}
		cout << ret << endl;
	}
}