企业网站备案信息查询,怎么在本地安装网站,网站建设怎么外包好,wap网站开发题目描述 环湖马拉松全程 L 公里#xff0c;已经安排了 N 个补给点#xff0c;位置已经确定。由于预算增加#xff0c;现在可以增设 K 个补给点。如何安排新增的补给点使得相邻补给点间最大距离最小。相邻补给点间距离也包括起点与第一个补给点之间的距离和最后一个补给点与…题目描述 环湖马拉松全程 L 公里已经安排了 N 个补给点位置已经确定。由于预算增加现在可以增设 K 个补给点。如何安排新增的补给点使得相邻补给点间最大距离最小。相邻补给点间距离也包括起点与第一个补给点之间的距离和最后一个补给点与终点之间的距离。
输入格式 输入文件名marathon.in
第一行包括 3 个整数 L,N,K分别表示马拉松全程长度、原有补给点的数量以及最多可以增设的补给点的数量。
第二行N 个整数表示原有的 N 个补给点的位置。补给点的位置用距离起点的距离表示取值范围 (0,L)。
输出格式 输出文件名marathon.out
一个整数意义如题所述表示相邻补给点间最大距离最小值。
输入输出样例
输入样例1
100 2 1
70 30
输出样例1
30说明 【数据范围】
0N≤100000
0≤L≤2000000000
0≤K≤2000000000 【解析】 给个赞有钱的捧个钱场。。支持小编继续努力下去。 标准的二分答案题因为有关键字最大值最小 二分的步骤 1题目问什么就对什么进行二分 2确定对象的范围 3枚举二分的数字是否符合题解
注意本题数据偏大使用C的输入输出和 long long
#include bits/stdc.h
using namespace std;
const int N1e510;
int L,n,k;
int a[N];
bool check(long long m){long long cnt0;for(int i1;in;i){int da[i]-a[i-1];//相邻两点之间的距离if(dm){cntceil(d/m);}}return cntk;
}
int main()
{scanf(%d%d%d,L,n,k);for(int i1;in;i){scanf(%d,a[i]);}sort(a1,an1);a[n1]L;n;long long l0,rL,m;while(lr){m(lr)1;if(check(m)){rm;}else{lm1;}}coutl;return 0;
}
