HBTU橙白时光P1103 最大的最小距离

HBTU橙白时光P1103 最大的最小距离

描述

在x轴正方向上随机选互不相同的n(2<=n<=100,000)个备用点，备用点所在位置均为整数，n个备用点编号为x1​,x2​,...,xn​(0<=xi​<=1,000,000,000)。

现在需要在上面n个备用点中选取c(2<=c<=n)个最终点，且希望任意两个最终点的最小距离尽可能的大，那么最大的最小距离是多少。

输入描述

有多组测试数据，以EOF结束。

第1行：空格分隔的两个整数n和c。

第2行 ~ 第n+1行：分别给出了编号x1​∼xn​的备用点位置，因为是随机选择的备用点，所以编号相邻与位置先后无关。

输出描述

对于每组测试数据输出一行，每行输出一个整数，表示该组测试数据最大的最小距离。

样例输入

5 3

1 2 8 4 9

输出

3

提炼一下题意就是：数轴上一系列整数，选择c个点作为终点，并且让他们尽可能地散开

思路：首先判断所选距离是否能够放得下足够的终点，若能则寻找是否有更大解，若没有则说明所选距离过大，则去寻找更小解

#include <iostream>
#include <algorithm>
using namespace std;const int N = 1e6 + 10;bool check(int n, int c, int x[], int distance) {int count = 1;  // 终点放置个数int last_pos = x[0];  // 上一个放置的最终点位置for (int i = 1; i < n; i++) {if (x[i] - last_pos >= distance) { //如果有其他点与上一个终点的距离>=参照值，就将该点放置，并更新为新的终点count += 1;last_pos = x[i];}if (count >= c) {return true; //点的个数满足要求}}return false;
}int main() {int n, c;while (cin >> n >> c) {int x[N];for (int i = 0; i < n; i++) {scanf("%d", &x[i]);}sort(x,x+n);int low = x[0];int high = x[n-1]-x[0];int ans = 0;while (low <= high) {int mid = low + high >> 1;if (check(n, c, x, mid)) {ans = mid;low = mid + 1;}//满足条件就在右边找有没有更大的，不满足就在左边去找更小的else{high = mid - 1;}}cout << ans << endl;}return 0;
}