在刷题时，总会遇到求最大值最小，最小值最大问题，也许它会暗喻是这样的一个问题。对于这样的一个问题，你会发现用dp和枚举都会超时超内存，或者说很麻烦，所以这是一个比较简单的解题方式。
二分逼近思想
•对于难以直接确定解的问题,采取二分枚举+检验的思想.
•已知解为x,验证x是否满足要求.
•如果答案具有特定的范围，并且验证答案是否成立的函数具有单调性。则可以在范围内对答案进行二分验证，从而快速确定答案。
对于答案判断：
在二分答案的时候需要判断，从而确定下一个范围。
可以用一个bool Check(x)函数来判断，返回true表示满足,返回false表示不满足.
可以类比数学函数f(x)>=0和f(x)<0来理解.
根据具体问题写出相应的Check函数往往就是解决问题的关键点。
下面举例一些问题：
poj2456
Aggressive cows
|
Time Limit: 1000MS |
|
Memory Limit: 65536K |
|
Total Submissions: 13139 |
|
Accepted: 6399 |
Description
Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).
His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?
Input
* Line 1: Two space-separated integers: N and C
* Lines 2..N+1: Line i+1 contains an integer stall location, xi
Output
* Line 1: One integer: the largest minimum distance
Sample Input
5 3
1
2
8
4
9
Sample Output
3
Hint
OUTPUT DETAILS:
FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.
Huge input data,scanf is recommended.
Source
USACO 2005 February Gold
2.题意概述：
农夫有c头牛，n个隔间，c头牛很躁动，很容易相互打架，因此农夫想把它们分得越远越好，要你分配隔间使得相邻两头牛的距离越远越好，问你这c头牛分割的最小距离的最大值。
3.解题思路：
先对隔间的坐标排序，对于牛，最小距离是0，最大距离不会超过两端两头牛的距离值，因此二分地查找分割距离的最大值，每次mid都judge一次，judge的时候贪心地放置牛，保证前i头牛是符合这样分割标准的。
AC代码：
#include<iostream>
#include<algorithm>
using namespace std;
int n,k,t;
int a[100000];
bool fun(int d){
int next,last=0,k=1;
for(int i=1;i<t;i++){
if(a[i]-a[last]>=d){
k++;
last=i;
}
}
if(k>=n)
return true;
else
return false;
}
int main(){
cin>>t;
cin>>n;
for(int i=0;i<t;i++)
cin>>a[i];
sort(a,a+t);
int l=0,r=a[t-1],mid=(l+r)/2;
while(l<=r){
if(fun(mid)){
l=mid+1;
}
else{
r=mid-1;
}
mid=(l+r)/2;
}
cout<<r<<endl;
return 0;
}
poj1505
Copying Books
|
Time Limit: 3000MS |
|
Memory Limit: 10000K |
|
Total Submissions: 9632 |
|
Accepted: 3013 |
Description
Before the invention of book-printing, it was very hard to make a copy of a book. All the contents had to be re-written by hand by so called scribers. The scriber had been given a book and after several months he finished its copy. One of the most famous scribers lived in the 15th century and his name was Xaverius Endricus Remius Ontius Xendrianus (Xerox). Anyway, the work was very annoying and boring. And the only way to speed it up was to hire more scribers.
Once upon a time, there was a theater ensemble that wanted to play famous Antique Tragedies. The scripts of these plays were divided into many books and actors needed more copies of them, of course. So they hired many scribers to make copies of these books. Imagine you have m books (numbered 1, 2 ... m) that may have different number of pages (p1, p2 ... pm) and you want to make one copy of each of them. Your task is to divide these books among k scribes, k <= m. Each book can be assigned to a single scriber only, and every scriber must get a continuous sequence of books. That means, there exists an increasing succession of numbers 0 = b0 < b1 < b2, ... < bk-1 <= bk = m such that i-th scriber gets a sequence of books with numbers between bi-1+1 and bi. The time needed to make a copy of all the books is determined by the scriber who was assigned the most work. Therefore, our goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment.
Input
The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly two lines. At the first line, there are two integers m and k, 1 <= k <= m <= 500. At the second line, there are integers p1, p2, ... pm separated by spaces. All these values are positive and less than 10000000.
Output
For each case, print exactly one line. The line must contain the input succession p1, p2, ... pm divided into exactly k parts such that the maximum sum of a single part should be as small as possible. Use the slash character ('/') to separate the parts. There must be exactly one space character between any two successive numbers and between the number and the slash.
If there is more than one solution, print the one that minimizes the work assigned to the first scriber, then to the second scriber etc. But each scriber must be assigned at least one book.
Sample Input
2
9 3
100 200 300 400 500 600 700 800 900
5 4
100 100 100 100 100
Sample Output
100 200 300 400 500 / 600 700 / 800 900
100 / 100 / 100 / 100 100
题意：按顺序给你N个数，将这N个数分成连续的M段，使得这M段每段的和中的最大值最小，输出最小值（1<=N<=100000,1<=M<=N,每个数在1到10000之间），如果有多种可能的话，尽量在前面进行划分。（其实第一次读题还不知道是什么意思，仔细琢磨才明白是这样的一个问题）
首先以正常的思路去考虑优化这个最大值的最小化问题，好像会陷入到循环之中找不到解决的思路，但是我们如果采用猜测－判断－重来的方法不断的去尝试二分查找最大值的最小值，然后去判断这个值是否合法，进一步优化这个值，就可以解决。
ac代码：
#include<iostream>
using namespace std;
int a[501];
int t,m,n;
int yes_no(int dis,int flag){
int last=0,next=0,tsum=a[last],cnt=1;
while(next<m){
if(tsum<=dis){
next++;
tsum=tsum+a[next];
}
if(tsum>dis){
cnt++;
last=next;
tsum=a[last];
}
}
// cout<<cnt<<endl;
if(cnt>flag)
return 2;
else if(cnt==flag)
return 1;
else
return 0;
}
int main(){
cin>>t;
while(t--){
int sum=0,ans;
cin>>m>>n;
for(int i=0;i<m;i++){
cin>>a[i];
sum+=a[i];
}
//cout<<sum<<endl;
int l=0,r=sum,mid;
//cout<<mid<<endl;
while(l<=r){
mid=(l+r)>>1;
if(yes_no(mid,n)==2){
l=mid+1;
//cout<<"1";
}
else if(yes_no(mid,n)==1){
ans=mid;
r=mid-1;
}
else{
r=mid-1;
// cout<<"2";
}
}
//cout<<ans<<endl;
int tsum=0;
int tn=n-1;
for(int i=0;i<m;i++){
tsum+=a[i];
if(tsum>=ans&&tn){
tn--;
cout<<" /";
tsum=a[i];
}
if(i==0){
cout<<a[i];
}
else
cout<<" "<<a[i];
} cout<<endl;
}
}
以上就是这两题，是基本的贪心+二分的求法。
注意：二分是在排序好的基础上进行的查找，所以，看清题目，尽量先排好序。。。
