CF 1260 D 题解

原题链接：

Problem - 1260D - Codeforces

题意：

你有 m 个士兵，你和士兵都在 0 坐标上，你要把其中的某些士兵带到 n+1 的坐标去打 boss，过程中不能死，每个士兵都有敏捷度 ，其中有 k 个陷阱，每个陷阱的坐标在  ，危险程度为  （当士兵的敏捷度 < 陷阱的危险程度时，士兵将立即死亡），你可以到  去解除这个陷阱的威胁，你在 x 坐标可以做如下操作：

1：你走到 x-1 或 x+1 的坐标，花费一个单位时间。

2：你和你的士兵 走到 x-1 或 x+1 的坐标，花费一个单位时间。

3：如果  ，你可以解除第 i 个陷阱。

（你和你的士兵可以不在同一个位置）

（陷阱的危险程度不会累加）

问你最多能带多少个士兵在 t 个单位时间内去打 boss。

解法：

二分答案。可以二分最多可以带的士兵数。右端点要设成 m + 1 （调了 1 h 就离谱）。

check 函数可以用一个变量来表示自己最远走到哪里，之后加上多走的就可以了。

Code ：

 # include <bits/stdc++.h>
//# include "windows.h"
# define ll long long
//# define int ll
# define db double
# define mod 998244353
//# define mod 1000000007
# define inf 1000000000
# define INF 1000000000000000000
# define fi first
# define se second
# define pb push_back
using namespace std;
int dx[15] = {0, 0, 1, -1, -1, -1, 1, 1};
int dy[15] = {1, -1, 0, 0, -1, 1, -1, 1};
 
int n, m, k, t, b[200005];
 
vector <pii> g[200005];
 
bool cmp1(int a, int b){
	return a > b;
}
 
int chk(int x){
	int num = b[x], ret = 0, ind = 0;
	for (int i = 1;i <= n+1;i++){
		ind = max(ind, i-1);
		ret++;
		if (g[i].size() == 0) continue;
		for (pii a : g[i]){
			int r = a.fi, w = a.se;
			if (w > num){
				if (ind >= r || i-1 >= r) continue;
				ret += 2*(r - max(ind, i-1));
				ind = max(ind, r);
			}
		}
	}
	return (ret <= t);
}
 
int main(){
	scanf("%d%d%d%d", &m, &n, &k, &t);
	for (int i = 1;i <= m;i++) scanf("%d", &b[i]);
	for (int i = 1;i <= k;i++){
		int l, r, d;
		scanf("%d%d%d", &l, &r, &d);
		g[l].pb({r, d});
	} 
	sort (b+1, b+m+1, cmp1);
	int l = 0, r = m+1;
	if (chk(l+1)) l++; 
	while (l < r-1){
		int mid = (l+r) >> 1;
		if (chk(mid)) l = mid;
		else r = mid; 
	}
	printf("%d", l);
	return 0;
}