A20205. 坐标选点
填空题
困难
知识点
题目描述
坐标选点
题目描述
修建了一条长度为 m 公里的铁路，起点和终点已经建有火车站。铁路沿线有 n 座城市（城市不位于起点或终点），第 i 座城市到铁路起点的距离为 ai 公里。
现在计划在这 n 座城市中选择 c 座修建火车站，使得所有火车站（包括起点和终点的火车站）之间的最小相邻距离尽可能大。请你计算这个最小相邻距离的最大可能值。
输入
第一行包含三个正整数n、c、m，分别表示城市数量、计划修建的火车站数量以及铁路总长度。
第二行包含n个正整数a1,a2,...,an，表示每座城市到铁路起点的距离。
输出
输出一个整数，表示最小相邻距离的最大可能值。
数据范围
1≤c≤n≤10^6，1≤ai<m≤10^9，输入中的所有数值均为整数。
输入样例1
5 3 10
1 2 8 4 9输出样例1
2参考答案
#include <bits/stdc++.h>
using namespace std;
int n, c, m, a[1000000] ;
bool check(int minDist) {
int count = 0; // 已经选择的中间火车站数量
int lastPos = 0; // 上一个火车站的位置（起点）
for (int i = 0; i < n; i++) {
if (a[i] - lastPos >= minDist) {
count++;
lastPos = a[i];
if (count >= c) break; // 已经选够
}
}
// 检查最后一个火车站到终点的距离是否满足
if (count >= c && (m - lastPos) >= minDist) {
return true;
}
return false;
}
int main() {
cin >> n >> c >> m;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a+n);
int low = 1, high = m, ans = 0;
while (low <= high) {
int mid = (low + high) / 2;
if (check(mid)) {
ans = mid;
low = mid + 1; // 尝试更大的距离
} else {
high = mid - 1;
}
}
cout << ans << endl;
return 0;
}
上一题
下一题