【二分答案】丢瓶盖

P1316 丢瓶盖

一题学会二分答案系列qwq

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #define sz 100010
 5 using namespace std;
 6 int n,m,ans=0,xz;
 7 int dis[sz];
 8 int judge(int x) {
 9     int i = 1, tot = 0, now = 1;
10     while(i < n) {
11         i++;
12         if(dis[i] - dis[now] < x) {
13     //        cout<<i<<' '<<now<<endl;
14             tot++;
15             continue;
16         }
17         else now = i;
18     }
19     return tot;
20 }
21 int main() {
22     scanf("%d%d",&n,&m);
23     xz = n-m;
24     int x = 0, y;
25     for(int i = 1; i <= n; i++) scanf("%d",&dis[i]);
26     sort(dis+1,dis+n+1);
27     int l = 1, r = dis[n];
28     while(l<=r) {
29         int mid = (l+r)>>1;
30     //    cout<<mid<<' ';
31         int abc = judge(mid);
32     //    cout<<abc<<endl;
33         if(abc <= xz){
34             ans = mid;
35             l = mid + 1;
36         }
37         else if(abc>xz) r = mid - 1;
38     }
39     cout<<ans;
40     return 0;
41 }

总之岁月漫长，然而值得期待。