首页 > 其他 > 详细

P1316 丢瓶盖--(二分答案)

时间:2019-03-20 00:19:59      阅读:73      评论:0      收藏:0      [点我收藏+]

标签:格式   class   algo   for   说明   d+   namespace   printf   ret   

题目描述

陶陶是个贪玩的孩子,他在地上丢了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<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\n",ans);
33     return 0;
34 }

 

P1316 丢瓶盖--(二分答案)

标签:格式   class   algo   for   说明   d+   namespace   printf   ret   

原文:https://www.cnblogs.com/Bravewtz/p/10562362.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 designnerd.net 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号