题目描述
公路上相邻路标的最大距离定义为该公路的“空旷指数”。现在决定在公路上增设一些路标,使得公路的“空旷指数”最小。计算能达到的最小值是多少。请注意,公路的起点和终点保证已设有路标,公路的长度为整数。
输入格式
第1行包括三个数L、N、K,分别表示公路的长度,原有路标的数量,以及最多可增设的路标数量。
第2行包括递增排列的N个整数,分别表示原有的N个路标的位置。路标的位置用距起点的距离表示,且一定位于区间[0,L]内。
输出格式
输出1行,包含一个整数,表示增设路标后能达到的最小“空旷指数”值。
输入输出样例
输入 #1
复制
101 2 1
0 101
输出 #1
复制
51
思路
在0到100之间保证空旷指数是19 需要100/19=5个路标
在0到100之间保证空旷指数是21需要100/21=4个路标
在0到100之间保证空旷指数是20需要100/20=5个路标?
错,只需要4个
sum += (dis[i] - dis[i - 1]) / mid;
if ((dis[i] - dis[i - 1]) % mid == 0)
sum--;
代码
#include<iostream>
#include<algorithm>
using namespace std;
int L, N, K;
int dis[10000000];
bool check(int mid)
{
int sum = 0;
for (int i = 1; i <= N; i++)
if (dis[i] - dis[i - 1] > mid)
{
sum += (dis[i] - dis[i - 1]) / mid;
if ((dis[i] - dis[i - 1]) % mid == 0)
sum--;
}
return sum <= K;
}
int main()
{
cin >> L >> N >> K;
for (int i = 1; i <= N; i++)
cin >> dis[i];
dis[0] = 0, dis[N + 1] = L;
int left = 0, right = L;
int mid, ans;
while (left <= right)
{
mid = (left + right) / 2;
if (check(mid))
right = (ans = mid) - 1;
else
left = mid + 1;
}
cout << ans << endl;
}
版权声明:本文为sdudyl原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。