LOJ P10011 愤怒的牛题解

每日一题 day36 打卡

Analysis

非常水的二分模板，就直接二分答案，用贪心策略check就好了

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define int long long
 6 #define maxn 100000+10
 7 #define rep(i,s,e) for(register int i=s;i<=e;++i)
 8 using namespace std;
 9 inline int read()
10 {
11     int x=0;
12     bool f=1;
13     char c=getchar();
14     for(; !isdigit(c); c=getchar()) if(c=='-') f=0;
15     for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
16     if(f) return x;
17     return 0-x;
18 }
19 inline void write(int x)
20 {
21     if(x<0){putchar('-');x=-x;}
22     if(x>9)write(x/10);
23     putchar(x%10+'0');
24 }
25 int n,m;
26 int x[maxn];
27 bool check(int dis)
28 {
29     int before=x[1],num=1;
30     for(int i=2;i<=n;i++)
31     {
32         if(x[i]-before<dis) continue;
33         ++num;
34         before=x[i];
35     }
36     if(num>=m) return true;
37     return false;
38 }
39 signed main()
40 {
41     n=read();m=read();
42     rep(i,1,n) 
43     {
44         x[i]=read();
45     }
46     sort(x+1,x+n+1);
47     int l=1,r=x[n],ans=0;
48     while(l<=r)
49     {
50         int mid=(l+r)>>1;
51         if(check(mid)==true) 
52             ans=mid,l=mid+1;
53         else if(check(mid)==false)
54             r=mid-1;
55     }
56     write(ans);
57     return 0;
58 }

请各位大佬斧正~~（反正我不认识斧正是什么意思）~~

LOJ P10011 愤怒的牛 题解

Analysis

LOJ P10011 愤怒的牛题解