P1316 丢瓶盖

admin

https://www.luogu.org/problemnew/show/P1316

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

输入输出格式
输入格式：
第一行，两个整数，A,B。（B<=A<=100000）

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

输出格式：
仅一个整数，为所求答案。

输入输出样例
输入样例#1：
5 3
1 2 3 4 5
输出样例#1：
2
说明
限时3秒

黄煦喆

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int n,c,l,r;
   
5. int a[100001];
   
6. int mid,ans,cnt,s,x;
   
7. int main()
   
8. {
   
9.     cin>>n>>c;
   
10.     for(int i=1;i<=n;i++)cin>>a[i];
    
11.     sort(a+1,a+n+1);
    
12.     r=a[n]-a[1];
    
13.     while(l<=r)
    
14.     {
    
15.         mid=l+r>>1;
    
16.         s=x=1;
    
17.         cnt=0;
    
18.         while(x<n)
    
19.         {
    
20.             x++;
    
21.             if(a[x]-a[s]<mid)cnt++;
    
22.             else s=x;
    
23.         }
    
24.         if(cnt+c<=n)
    
25.         {
    
26.             ans=mid;
    
27.             l=mid+1;
    
28.         }
    
29.         else r=mid-1;
    
30.     }
    
31.     cout<<ans;
    
32.     return 0;
    
33. }
    

复制代码