河中跳房子

题意

最多移走 $M$ 块中间石头，使从起点到终点的最短一次跳跃距离尽量大。

思路

二分候选最短距离 distance。从左到右扫描，当前石头与上一个保留位置的距离不足时必须删除一个，贪心地计数即可得到满足该距离至少需要删多少块。若不超过 $M$ ，该距离可行。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25river_length, rock_count, removal_limit = map(int, input().split())
rocks = [0] + [int(input()) for _ in range(rock_count)] + [river_length]


def can_keep_minimum_distance(distance: int) -> bool:
    removed = 0
    previous = 0
    for position in rocks[1:]:
        if position - previous < distance:
            removed += 1
        else:
            previous = position
    # 最后一次不足时，计数等价于删去最后保留的石头；后面已无石头，不影响计数。
    return removed <= removal_limit


low, high = 1, river_length
while low < high:
    middle = (low + high + 1) // 2
    if can_keep_minimum_distance(middle):
        low = middle
    else:
        high = middle - 1

print(low)

C++代码

cpp

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5+5;
int a[maxn];
int L;
int n;
int m;
bool check(long long min_jump){
    int pre = 0; //上一个没有删除的石头的下标
    int cnt = 0;
    for(int i =1;i<=n;i++) {
        if( a[i] - a[pre] < min_jump)
        {
            cnt++;
            if( cnt > m) return 0; //超过了删除的石头的个数
        }
        else {
            pre = i; //当前作为不删除的上一个石头的下标
        }
    }

    //特判，
    if( a[n+1] - a[pre] < min_jump) {
        cnt++;
    }
    if (cnt > m)
        return 0;
    return 1;
}

long long bs_find(long long l,long long r) {
    while( l < r) {
        long long mid = (l+r) >>1;
        
        if( !check(mid) ) 
            r = mid;
        else
            l = mid+1;
    }
    return l;
}

void init() {
    cin >> L >> n >> m;
    a[0] = 0;
    for(int i =1;i<=n;i++)
        cin >> a[i];    
    a[n+1] = L;
}

int main() {
    init();
    int ans = bs_find(1,1e9+5);
    cout << ans - 1;
    // for(int i=1;i<=11;i++) {
    //     cout << i << " " << check(i) << endl;
    // }
    return 0;
}

复杂度

时间复杂度为 $O(n \log L)$ ，空间复杂度为 $O(n)$ 。

总结

最大化最小跳跃距离是典型的二分答案问题，判定过程由局部贪心完成。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结