题目链接:Click here~~
题意:
一条线段上有 n 个点,选取 m 个点,使得相邻点之间的最小距离值最大。
解题思路:
和上道题类似,对于某个最小距离值 d ,如果 d 能满足要求,设 d' < d,那么 d' 也一定能满足要求。而问题的解就是那个满足要求的最大的 d。
那么,如何判断对于某个最小距离值 d 能否满足要求呢?
首先,选取边界的点是明智的。
假设有一种满足要求的方案 F ,且 F 中没有选取边界点。那么我将方案 F 中最靠近边界的那个点换成边界点,一定不会影响方案的满足性。反之,则不然。
确定了一个点以后,之后就很好判断了,每次选点时选离当前点最近的且满足距离值大于等于 d 的,最后判断能否取够 m 个点即可。
于是问题可转化为二分模型求解。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int L,n,m,pos[100005]; bool can(int l) { int cnt = 1 , cur = pos[0]; for(int i=1;i<n;i++) { while(i<n && pos[i]-cur<l) i++; cur = pos[i]; if(i<n && ++cnt == m) return true; } return false; } int main() { while(~scanf("%d%d",&n,&m)) { for(int i=0;i<n;i++) scanf("%d",&pos[i]); sort(pos,pos+n); int l = 0, r = pos[n-1]-pos[0]+1; //details while(l < r) { int mid = (l+r)/2; if(can(mid)) l = mid+1; else r = mid; } printf("%d\n",l-1); } return 0; }