80pts,WA#5 #8求助
查看原帖
80pts,WA#5 #8求助
1285350
AIcat_136楼主2024/8/11 17:30

不知道哪里错了(不要误会注释,这不是tj代码

#include <bits/stdc++.h>
using namespace std;
int len, n, k;
int a[114514];

bool check(int x) 
{
    int cnt = 0; // 需要增设的路标数
    int pre = a[0]; // 上一个设定的路标位置
    for(int i = 1; i < n; i++) 
    {
        if(a[i] - pre > x) 
        {
            // 在pre和a[i]之间增设路标
            int t = (a[i] - pre - 1) / x;
            cnt += t;
            if(cnt > k) 
                return false; // 如果需要的路标数超过k,不可行
        }
        pre = a[i];
    }
    return true;
}

int main() 
{
    cin >> len >> n >> k;
    for(int i = 1; i <= n; i++) 
        cin >> a[i];
    int l = 1; // 最小可能的最大距离
    int r = len; // 最大可能的最大距离
    int ans = len;
    while(l <= r) 
    {
        int mid = (l + r) / 2;
        if(check(mid)) 
        {
            ans = mid; // 尝试更小的最大距离
            r = mid - 1;
        } 
        else 
            l = mid + 1;
    }
    cout << ans << endl;
    return 0;
}
/*
输入与初始化:
    读取公路长度 L、原有路标数量 N 和
最多可增设的路标数量 K,以及路标的位置。
------
check函数:
    该函数检查在最大距离为 x 时,是否能在增设不超过 k 个
路标的情况下覆盖所有路标。如果可以,则返回 true,否则返回 false。
------
二分查找:
    在 [1, L] 范围内进行二分查找,找到最小的满足条件的 x。
*/
2024/8/11 17:30
加载中...