P3853. 路标设置

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

考点

  • 二分

题解

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

using namespace std;

const int LEN = 1e5 + 10;

typedef long long ll;

int L, N, M;

double arr[LEN];

bool check(int x)
{
    ll res = 0;
    for (int i = 0; i < N - 1; ++i)
        res += ceil((arr[i + 1] - arr[i]) / x) - 1;
    return res <= M;
}

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

思路

根据题眼，要我们求相邻路标的最大距离的最小值；DP/贪心/二分依次判断，只可能是二分（因为并没有什么明显的状态转移与单调性）

直接二分相邻路标的最大距离，左端点为1，右端点为L

  • 每次从左到右遍历，向上取整(相邻路标之间的距离 / 当前要求的最大距离) - 1

    就是相邻路标之间还能插几个新路标

  • 当前结果小于M，说明最大距离太大了，应该缩小（向左端点移动）

  • 当前结果等于M，也要向左端点移动（因为题目要找满足要求中的最小值）

  • 当前结果大于M，说明最大距离太小了，应该增大（向右端点移动）