题目链接:https://www.luogu.com.cn/problem/P1824
最小间距的最大值，二分模板
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 1000010; int n, m, t; int a[N]; bool check(int x){ //x为最终结果，及最小间距的最大空间 int num = 0; int l = a[1];//第一只牛的位置 for (int i = 2; i <= n; i ++ ){ //当前值小于结果，那就在下一个牛栏放牛 if (a[i] - l < x) num ++; else l = a[i];//不然就是满足，在这放牛 if (num > t) return false; //牛栏数多余题目要求就要舍弃 } return true; } int main(){ cin >> n >> m; for (int i = 1; i <= n; i ++ ) cin >> a[i]; sort(a+1, a+1+n); t = n - m;//最大剩余牛栏数 int l = 1, r = a[n] - a[1];//二分的左右边界 while (l < r){ int mid = (l + r + 1) >> 1; if (check(mid)) l = mid;//答案可行，追求更大的 else r = mid - 1;//答案不可行，找存在的答案 //cout << l << ' ' << r << endl; } if (check(r)) cout << r << endl; else cout << l << endl; return 0; }