下面是一本通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\n",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 }
原文：https://www.cnblogs.com/juruohqk/p/10991642.html