二分法

二分搜索法，是通过不断缩小解可能存在的范围，从而求得问题最优解的方法。

1.从有序数组中查找某个值

STL以lower_bound函数的形式实现了二分搜索。类似方法还有upper_bound

2.假定一个解并判断是否可行

注意输出答案的格式

3.最大化最小值

找到最大的d使得最近的两头牛的距离不小于d

(1)对牛舍的位置x排序

(2)第一头牛进x0

(3)若第i头放入了xj，则第i+1头放入满足xk-xj>=d的最小的xk

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<math.h>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 int n,m;
 8 double L[100005];
 9 bool judge(int len)
10 {
11     int last=0;
12     for(int i=1;i<m;i++)
13     {
14         int cur=last+1;
15         while(cur<n&&L[cur]-L[last]<len) cur++;
16         if(cur==n) return false;
17         last=cur;
18     }
19     return true;
20 }
21 int main()
22 {
23     cin>>n>>m;
24     for(int i=0;i<n;i++) cin>>L[i];
25     //sort(L,L+n);
26     int l=0,r=100000005;
27     while(r-l>1)
28     {
29         int mid=(l+r)/2;
30         if(judge(mid)) l=mid;
31         else r=mid;
32     }
33     cout<<l<<endl;
34     return 0;
35 }

View Code

4.最大化平均值