本文主要是介绍P1316 丢瓶盖（二分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：https://www.luogu.com.cn/problem/P1316
A个点再一条直线上，从中挑选B个，使得距离最近的2个距离最大，问距离最大可以是多少？
Solve： 二分答案
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 7;
int n, m;
int a[MAXN];
bool judge(int mid)
{int cnt = 1; //记录选取了几个点int dis = 0;//两点之间的距离int start = 1;//起点for(int i = 1; i <= n; i++){if(a[i] - a[start] <= mid) dis = max(dis, a[i] - a[i - 1]);else{cnt++;start = i;dis = 0;}}if(cnt >= m) return true;return false;
}
int main()
{scanf("%d %d", &n, &m);for(int i = 1; i<= n; i++){scanf("%d", &a[i]);}sort(a + 1, a + 1 + n);int l = INF, r = 0;for(int i = 1; i <= n; i++)l = min(l, a[i] - a[i - 1]);r = a[n] - a[1];while(l <= r){int mid = (l + r) >> 1;if(judge(mid)) l = mid + 1;else r = mid - 1;}printf("%d\n", l);return 0;
}
类似题目： https://www.luogu.com.cn/problem/P1182 （题解点我）
这篇关于P1316 丢瓶盖（二分）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
