链接
题意：n个士兵能力值为ai，有m个陷阱，每个陷阱有l，r，d三个属性，l代表陷阱的位置，r是可以使陷阱失效的位置，士兵能力值小于d的不可以经过l，现在你和n个士兵位于坐标轴0点，boss位于k+1点，每次单独移动和带士兵移动一格（左右）花费的时间为1，求在时间t内最多能带多少个士兵到boss点。
(1≤m,n,k,t≤2?10^ 5 ,k<t)
首先对能力值的最小值二分
对于每次二分，时间可以分为两部分，一是带士兵从坐标0到坐标k+1的时间t1=k+1，二是因为要使陷阱失效来回的时间t2；让t2最小的贪心策略是每次处理尽可能多的连续陷阱区间，陷阱按l坐标升序排序，记录选取的陷阱的r最大值rmax，然后每次比较下一个陷阱的r值，如果ri<=rmax，说明该陷阱位于连续区间内；如果ri>rmax，此时若li<=rmax,说明该陷阱还在上一处理的连续区间内，更新rmax值为ri，t2加上2*(ri-rmax)，如果li>rmax说明该陷阱位于一个新区间，t2加上2*(ri-(li-1))
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int m, n, k, t;
int a[200005];
struct node
{int l, r, d;
}b[200005];
int main()
{while (cin >> n >> k >> m >> t){for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);sort(a + 1, a + 1 + n);for (int i = 1; i <= m; i++)scanf("%d%d%d", &b[i].l, &b[i].r, &b[i].d);sort(b + 1, b + 1 + m, [](node x, node y) {return x.l < y.l; });int l = 1, r = n;int ans = 0;while (l <= r){int mid = (l + r) / 2;int z = a[n - mid + 1];int la = 0;//上次的位置int sum = 0;ll cnt = 0;for (int i = 1; i <= m; i++){if (b[i].d <= z)continue;if (b[i].r <= la)continue;if (la < b[i].l)la = b[i].l - 1;sum += b[i].r - la;la = b[i].r;}cnt = 2ll * sum + k + 1;//cout << mid <<"***"<< cnt << endl;if (cnt <= t){ans = mid;l = mid + 1;}else r = mid - 1;}cout << ans << endl;}
}