洛谷 P1316 丢瓶盖

题目描述

陶陶是个贪玩的孩子，他在地上丢了A个瓶盖，为了简化问题，我们可以当作这A个瓶盖丢在一条直线上，现在他想从这些瓶盖里找出B个，使得距离最近的2个距离最大，他想知道，最大可以到多少呢？

输入输出格式

输入格式：

第一行，两个整数，A,B。（B<=A<=100000）

第二行，A个整数，分别为这A个瓶盖坐标。

输出格式：

仅一个整数，为所求答案。

输入输出样例

输入样例#1： 5 3 1 2 3 4 5 输出样例#1： 2

说明

限时3秒

比跳石头那个题多了个排序，其他的都一样，然而新的二分写法总是有些不适应。 #include<algorithm> #include<iostream> #include<cstdio> using namespace std; const int N=100005; int n,m,a[N]; bool bin(int lim) { int lst=1,cnt=0; for(int i=2;i<=n;i++) { if(a[i]-a[lst]<lim) cnt++; else lst=i; } if(cnt<=n-m) return 1; return 0; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); int l=0,r=a[n]-a[1],mid; while(l<r) { mid=(l+r)/2+1; if(bin(mid)) l=mid; else r=mid-1; } printf("%d\n",l); return 0; }