P1316 丢瓶盖--（二分答案）

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

输入样例#1：复制

5 3
1 2 3 4 5

输出样例#1：复制

说明

限时3秒

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn = 1e5+10;
 7 int a[maxn];
 8 int n,m;
 9 
10 int main(){
11     scanf("%d%d",&n,&m);
12     for( int i=1; i<=n; i++ ){
13         scanf("%d",&a[i]);
14     }
15     sort(a+1,a+1+n);
16     int ans=0;
17     int l=0,r=a[n];
18     
19     while(l<=r){
20         int mid=l+(r-l)/2;
21         int pos=1;
22         int s=1;
23         for( int i=2; i<=n; i++ ){
24             if(a[i]-a[pos]>=mid) pos=i,s++;
25         } 
26         if(s>=m){
27             ans=mid;
28             l=mid+1;
29         }
30         else r=mid-1;
31     }
32     printf("%d
",ans);
33     return 0;
34 }

有些目标看似很遥远，但只要付出足够多的努力，这一切总有可能实现！