AtCoder-abc230_d 题解

发表于2023-05-18更新于2023-05-18

题目传送门

一道贪心题……

我们可以将每一堵墙的右端点从小到大进行排序，然后我们从第 11 堵墙开始看，将在第 11 堵墙的右端点打破后会倒塌的墙全部跳过，去看下一堵还没被打破的墙。可以证明这是最优解。

Code

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
36
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
int n, d, ans;
struct xvl_ {
    int l, r;
    bool operator < (const xvl_& s) const {
        return r < s.r;
    }
}a[200005];
signed main() {
    ios :: sync_with_stdio(0);
    cin >> n >> d;
    for (int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r;
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; ans++) {
        int bk = i + 1; 
        while (a[bk].l <= a[i].r + d - 1 and bk <= n) bk++;
        i = bk; // 前面的墙被打破了
    }
    cout << ans;
    return 0;
}

/*
0 1 2 3 4 5 7 8 9 …
1 ---
2       -----
3         -------

0 1 2 3 4 5 7 8 9 …
1 ---
2       -----
3       ---------
*/