不知道哪里错了(不要误会注释,这不是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。
*/