洛谷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 ",l) ; 50 return 0 ; 51 }