NOIP2015跳石头 做题笔记

发表于 | 更新于 | | 阅读次数：

这题是二分+贪心，关键在于贪心策略，移走石头即合并线段，从左向右扫描一个坐标区间，如果长度合适（大于等于二分的答案）就移动左端点，不合适就固定左端点同时进行一次合并（计数器加一），如果合并次数在m以内就认为存在一个方案。

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
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 50009;
int d[maxn];
int L, m, n;
bool check(int mid) {
    int left = 0, cnt = 0;
    for(int i = 1; i <= n + 1; i++) {
        if(d[i] - left < mid) cnt++;
        else left = d[i];
    }
    if(cnt > m) return 0;
    else return 1;
}
int main() {
    scanf("%d%d%d", &L, &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", d + i);
    }
    d[n + 1] = L;
    int l = 1, r = L;
    while(l < r) {
        int mid = (l + r + 1) >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    printf("%d", l);
}