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

74 阅读 0 评论 49 点赞

我是靠谱客的博主可爱康乃馨，这篇文章主要介绍Codeforces 1260D A Game with Traps（二分查找），现在分享给大家，希望可以做个参考。

思路：

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

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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;
}