首页 > 其他 > 详细

洛谷P1316 丢瓶盖 二分答案

时间:2017-07-21 09:47:47      阅读:382      评论:0      收藏:0      [点我收藏+]

洛谷P1316 丢瓶盖
二分答案
二分距离
判断能够取几个

 

 1 #include <bits/stdc++.h> 
 2 #define For(i,j,k) for(int i=j;i<=k;i++)
 3 using namespace std ; 
 4 
 5 const int N = 100011 ; 
 6 int n,k,mi,mx,mid,l,r ; 
 7 int last,sum ; 
 8 int pos[N] ; 
 9 
10 inline int read() 
11 {
12     int x = 0 , f = 1 ; 
13     char ch = getchar() ; 
14     while(ch<0||ch>9) { if(ch==-) f = -1 ; ch = getchar(); } 
15     while(ch>=0&&ch<=9) { x = x * 10+ch-48 ; ch = getchar(); } 
16     return x * f ; 
17 }
18 
19 inline bool check(int mid) 
20 {
21     last = pos[ 1 ] ; 
22     sum = 1 ; 
23     For(i,2,n) 
24         if( pos[ i ] - last >= mid ) 
25             last = pos[ i ],sum++ ;  
26     return sum>=k ; 
27 }
28 
29 int main() 
30 {
31     n = read() ; k = read() ; 
32     mx = mi = pos[ 1 ] = read() ; 
33     For(i,2,n) 
34     {
35         pos[ i ] = read() ; 
36         if( mi > pos[ i ] ) mi = pos[ i ] ; 
37         if( mx < pos[ i ] ) mx = pos[ i ] ; 
38     }
39     sort(pos+1,pos+n+1) ; 
40     l = 0 ;  r = mx - mi ; 
41     while( l < r ) 
42     {
43         mid = ( l + r+1 ) >>1 ; 
44         if(check(mid)) 
45             l = mid ;  
46         else
47             r = mid-1 ; 
48     }
49     printf("%d\n",l) ; 
50     return 0 ; 
51 }

 

洛谷P1316 丢瓶盖 二分答案

原文:http://www.cnblogs.com/third2333/p/7215818.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!