牛客课后1.2 糖糖别胡说，我真的不是签到题目 题解

题目大意

有n个人，分成两队，排成一条，从小到大选人，选到第i个人的时候，可以杀死他前面所有和他不是同一个队的小于他能力值的人。恰巧有人会发功，在选到第i人之后，会让1~i的人的能力值加一，求最后剩下的人数。

解题思路

刚开始想到用暴力二分搜加差分写，虽然知道应该会T，但是还是试着写了一下。

果不其然。。

后面想了好久，真的想不到了，看的题解。

（我太菜了。。

发现有一个很重要的点，就是对于某个点来说，用这个点的能力与在这个点之前发功修改的能力去比和用这两个点在所有发功结束的能力之比，是一样的。

所以就只需要求出所有修改之后的值，从后往前枚举，维护两个组的最小值即可。

不得不说，某些时候，思维题比算法题难多了。

（是真的想不到。。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

struct ty {
	ll x, e;
};
int h[500500], sum[500500];
ty num[500500];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		int n, m; cin >> n >> m;
		memset(sum, 0, sizeof(sum));
		for (int i = 1; i <= n; i++) {
			ll a, b; cin >> a >> b;
			num[i] = { a,b };
		}
		for (int i = 1; i <= m; i++) {
			cin >> h[i];
			sum[1]++, sum[h[i] + 1]--;
		}
		ll ans = n, max0, max1;
		max0 = max1 = 0;
		for (int i = 1; i <= n; i++) {
			sum[i] += sum[i - 1];
			num[i].e += sum[i];
		}
		for (int i = n; i > 0; i--) {
			if (num[i].x) {
				if (num[i].e <= max0) ans--;
				max1 = max(max1, num[i].e);
			}
			else {
				if (num[i].e <= max1) ans--;
				max0 = max(max0, num[i].e);
			}
		}
		cout << ans << endl;
	}
}