洛谷P1316 丢瓶盖

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

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

说明

限时3秒

二分答案+贪心。。。

附代码：

#include<iostream> #include<algorithm> #include<cstdio> #define MAXN 100010 using namespace std; int n,m,a[MAXN]; inline int read(){ int date=0,w=1;char c=0; while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();} while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();} return date*w; } bool check(int x){ int s=1,d=a[1]; for(int i=2;i<=n;i++){ if(a[i]-d<x)continue; d=a[i]; s++; } if(s<m)return false; return true; } int main(){ int l=2147483647,r,mid; n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); sort(a+1,a+n+1); for(int i=2;i<=n;i++)l=min(l,a[i]-a[i-1]); r=a[n]-a[1]; while(l<=r){ mid=l+r>>1; if(check(mid))l=mid+1; else r=mid-1; } printf("%d\n",l-1); return 0; }