codeforces1260D A Game with Traps（二分/差分）

题目链接：codeforces 1260D

题目思路：

求尽可能多的人数，在规定时间内到那目的地，对人数进行二分即可，并且每次带的人敏捷值尽可能高。假设当前人数为 $x$，最低的敏捷值为 $y$。如何求得当前所要花费的最少时间呢？可以用一个差分数组标记，然后通过前缀和计算时间。具体参见代码。

参考代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

struct Node {
   
	int l, r, d;	
}node[N];
int a[N];
int n, m, k, t;
map<int, int> mp;

bool check(int x, int y) {
   
	int T = 0;
	mp.clear();
	for (int i = 1; i <= k; i++) {
   
		if (node[i].d > y) {
    // 如果该段危险值大于下限，加上这段
			mp[node[i].l]++;
			mp[node[i].r+1]--;
		}
	}
	int pre = 0; // 前缀和
	for (int i = 1; i <= n+1; i++) {
   
		pre += mp[i];
		if (pre >= 1) {
    // 如果当前位置大于等于1，说明要先摧毁陷阱，故在这个点上花费的时间为3
			T += 3;
		} else {
   
			T++;
		}
	}
	return T <= t;
}


int main() {
   

	cin >> m >> n >> k >> t;
	for (int i = 1; i <= m; i++) cin >> a[i];
	for (int i = 1; i <= k; i++) {
   
		cin >> node[i].l >> node[i].r >> node[i].d;
	}
	sort(a+1, a+1+m, greater<int>());
	int l = 0, r = m, mid;
	while (l < r) {
   
		mid = (l+r+1) >> 1; // 这里要注意向上取整，即相邻的数优先判断大的是否满足条件
		if (check(mid, a[mid])) {
   
			l = mid;
		} else {
   
			r = mid - 1;
		}

	}
	cout << l << endl;

	return 0;
}