Codeforces 1260D A Game with Traps（二分查找）

思路：

1.首先贪心，我们肯定需要从$d$大的怪物开始消灭；
2.设自己在$t$的限制内可以消灭所有$d$大于$rs$的怪物，我们二分查找出最小的$rs$，然后遍历整个士兵数组查询哪些士兵符合就ok了~

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 5;
int m, n, k, t;
int a[MAX_N], l[MAX_N], r[MAX_N], d[MAX_N];
bool ok(int val) {
vector<int> v(n + 1);
for (int i = 0; i < k; i++) if (d[i] > val) {
v[l[i] - 1]++;
v[r[i]]--;
}
for (int i = 1; i <= n; i++) v[i] += v[i - 1];
int ans = n + 1;
for (int i = 0; i <= n; i++) if (v[i]) ans += 2;
//	cerr << val << ' ' << ans << endl;
return ans <= t;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> m >> n >> k >> t;
for (int i = 0; i < m; i++) cin >> a[i];
for (int i = 0; i < k; i++) cin >> l[i] >> r[i] >> d[i];
int lf = 0, rt = MAX_N, rs = -1;
while (lf <= rt) {
int mid = (lf + rt) >> 1;
if (ok(mid)) rs = mid, rt = mid - 1;
else lf = mid + 1;
}
int ans = 0;
for (int i = 0; i < m; i++) if (a[i] >= rs) ans++;
cout << ans;
return 0;
}

最后

以上就是可爱康乃馨为你收集整理的Codeforces 1260D A Game with Traps（二分查找）的全部内容，希望文章能够帮你解决Codeforces 1260D A Game with Traps（二分查找）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。