P2678. 跳石头

发表于 分类于 阅读次数： Waline： 本文字数： 482 阅读时长 ≈ 2 分钟

考点

  • 贪心
  • 二分

题解

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
#include <bits/stdc++.h>

using namespace std;

const int LEN = 5e4 + 10;

typedef long long ll;

int L, N, M, arr[LEN];

bool check(int x)
{
    int cnt = 0, pre = 0;
    for (int i = 0; i <= N; ++i)
    {
        if (arr[i] - pre < x)
            ++cnt;
        else
            pre = arr[i];
    }
    return cnt <= M;
}

int main()
{
    cin >> L >> N >> M;
    for (int i = 0; i < N; ++i)
        cin >> arr[i];
    arr[N] = L;
    int l = 1, r = L;
    while (l <= r)
    {
        int mid = l + (r - l) / 2;
        if (check(mid))
            l = mid + 1;
        else
            r = mid - 1;
    }
    cout << r;
    return 0;
}

思路

根据题眼最短跳跃距离的最大值，很容易想到DP/贪心/二分

  • DP：设二维数组dp[i][j]，表示在前i块石头移走j块石头的最短距离；但石头太多，数组可能会炸
  • 贪心：每次搬走最短跳跃距离的石头，但是需要用堆来存储，时间复杂度可能吃不消

重点讲一下二分的思路，直接二分最短跳跃距离，左端点为1，右端点为L

从左往右遍历石头数组，若当前石头到上一个石头的距离小于当前最短跳跃距离，就把它移走

为什么前后两个石头，就移后面的呢？

前面的石头与前前面的石头已经大于等于最短跳跃距离了，所以移前面的石头根本没有意义

还有一个坑点，一定要把终点加入石头数组，也就是这行代码

1
arr[N] = L;

你肯定会问，“刚才说移后面的石头，终点加进去了，岂不是终点也有可能被移走？”

代码层面上解释，终点确实“被移走”；但是换个角度来看，可以看作是终点的前一块石头被移走呢

方才提过，前面的石头已经满足条件，再对其进行操作是无意义的，并不影响结果

比如这组Hack数据，答案应为2

1
2
3
4
8 3 1
2
4
7