高级算法--二分

下面是一本通OJ上面的题目代码

·例一：

题目描述：

　　农夫 John 建造了一座很长的畜栏，它包括N (2 ≤ N ≤ 100,000)个隔间，这些小隔间依次编号为x1,...,xN (0 ≤ xi ≤ 1,000,000,000). 但是，John的C (2 ≤ C ≤ N)头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢

代码实现：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 const int N=1e5+3;
 8 int n,m,x[N];
 9 
10 inline bool check(int d)
11 {
12     int cow=1;
13     int rgt=x[1]+d;
14     for(int i=2;i<=n;++i)
15     {
16         if(x[i]<rgt) continue;
17         ++cow;
18         rgt=x[i]+d;
19     }
20     return cow>=m;
21 }
22 
23 int main()
24 {
25     scanf("%d%d",&n,&m);
26     for(int i=1;i<=n;++i)
27         scanf("%d",&x[i]);
28     sort(x+1,x+n+1);
29     int l=0,r=x[n]-x[1];
30     while(l<=r)
31     {
32         int mid=l+r>>1;
33         if(check(mid)) l=mid+1;
34         else r=mid-1;
35     }
36     printf("%d
",r);
37     return 0;
38 }

·例二

题目描述：

　　给定一个长度为n的正整数序列A。求一个平均数最大的，长度不小于L的子序列。

代码实现：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 
 8 double a[100001],b[100001],sum[100001];
 9 
10 int main()
11 {
12     int N,L;
13     scanf("%d%d",&N,&L);
14     for(int i=1;i<=N;++i) scanf("%lf",&a[i]);
15     double eps=1e-5;
16     double l=-1e6,r=1e6;
17     while(r-l>eps)
18     {
19         double mid=(l+r)/2;
20         for(int i=1;i<=N;++i) b[i]=a[i]-mid;
21         for(int i=1;i<=N;++i) sum[i]=sum[i-1]+b[i];
22         double ans=-1e10;
23         double min_val=1e10;
24         for(int i=L;i<=N;++i)
25         {
26             min_val=min(min_val,sum[i-L]);
27             ans=max(ans,sum[i]-min_val);
28         }
29         if(ans>=0) l=mid;
30         else r=mid;
31     }
32     printf("%d",int(r*1000));
33     return 0;
34 }