问题 S: 【基础】最小的空旷指数

Question

问题 S: 【基础】最小的空旷指数

题目描述
A市和B市之间有一条长长的高速公路，这条公路的某些地方设有路标，但是大家都感觉路标设得太少了，相邻两个路标之间往往隔着相当长的一段距离。为了便于研究这个问题，我们把公路上相邻路标的最大距离定义为该公路的“空旷指数”。

现在政府决定在公路上增设一些路标，使得公路的“空旷指数”最小。他们请求你设计一个程序计算能达到的最小值是多少。请注意，公路的起点和终点保证已设有路标，公路的长度为整数，并且原有路标和新设路标都必须距起点整数个单位距离。

输入
第1行包括三个数L、N、K，分别表示公路的长度，原有路标的数量，以及最多可增设的路标数量。
第2行包括N个整数（这N个数并未排序），分别表示原有的N个路标的位置。路标的位置用距起点的距离表示，且一定位于区间[0,L]内。
数据范围：
50%的数据中，2 ≤ N ≤100，0 ≤K ≤100
100%的数据中，2 ≤N ≤100000, 0 ≤K ≤100000
100%的数据中，0 ＜ L ≤10000000
输出
输出1行，包含一个整数，表示增设路标后能达到的最小“空旷指数”值。
样例输入 Copy
101 2 1
0 101
样例输出 Copy
51
提示
样例说明:
公路原来只在起点和终点处有两个路标，现在允许新增一个路标，应该把新路标设在距起点50或51个单位距离处，这样能达到最小的空旷指数51。
代码（时间超限）

#include<bits/stdc++.h>
using namespace std;
int l,r,mid,L,n,k,a[1000000];
bool chazhao(int ans) { //判断空旷指数可不可行
    int last=0,cnt=0;
    for(int i=2; i<=n; i++) {
        while(a[i]-last>ans) {
            last+=ans;
            cnt++;
        }
        last=a[i];
    }
    return cnt>k;
}
int main() {
    int ans=0;
    scanf("%d%d%d",&L,&n,&k);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    l=0,r=L;
    while(l<r) {
        mid=l+(r-l)/2;
        if(chazhao(mid))l=mid+1;
        else r=mid-1,ans=mid;
    }
    printf("%d",ans);
    return 0;
} 

Answer 1

引自免费微信小程序：皆我百晓生

根据您提供的代码，我发现主要的问题在于搜索最小空旷指数的方法效率较低，导致了时间超时。这里可以采用二分查找法来优化搜索过程，但我们需要调整一下查找函数chazhao的逻辑，使其返回的是可能的最大路标数量，而不是检查是否满足给定的空旷指数。具体来说，我们需要找到最大的ans，使得添加不超过k个新的路标就能覆盖所有原有的路标间隔。

以下是修改后的代码：

#include <bits/stdc++.h>
using namespace std;

// 新的查找函数，返回在给定空旷指数下能容纳的最大路标数量
int findMaxCount(int ans) {
    int last = 0, cnt = n - 1;
    for (int i = 2; i <= n; i++) {
        while (a[i] - last > ans) {
            last += ans;
            cnt--;
        }
        last = a[i];
    }
    return cnt;
}

int main() {
    int L, n, k, ans = 0;
    scanf("%d%d%d", &L, &n, &k);
    vector<int> a(n + 2); // 使用vector存储路标位置，方便操作
    a[0] = 0;
    a[n + 1] = L; // 添加起点和终点的路标
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    sort(a.begin(), a.end()); // 排序路标位置，以便后续处理

    int l = 1, r = L; // 二分查找的边界
    while (l < r) {
        int mid = l + (r - l) / 2;
        int maxCount = findMaxCount(mid);
        if (maxCount >= k)
            l = mid + 1;
        else
            r = mid;
    }

    ans = l - 1; // 最终答案是比l小1的值，因为l已经是满足条件的最大空旷指数
    printf("%d", ans);
    return 0;
}

这段代码首先对原有的路标位置进行排序，然后使用二分查找法来寻找最小的空旷指数。同时，我们添加了起点和终点的路标，确保它们始终存在。通过findMaxCount函数，我们可以快速找到在给定空旷指数下能容纳的最大路标数量。当这个数量大于等于k时，我们知道可以通过增加路标来达到更小的空旷指数，因此将左边界更新为当前中间值加一。否则，我们将右边界更新为当前中间值减一。最终，二分查找结束后，l - 1即为所求的最小空旷指数。