二分答案是一种神奇的思想。对于一道题，与通常的求解答案不同，二分答案的思想是“猜出”答案，使用得当会十分巧妙。
它的思想大致与对分查找类似，所以对于求解的题目需要满足一些条件：
- 答案要有一定的范围
- 答案要有单调性
- 要能快速验证猜的答案的正确性
因为二分了复杂度是猜答案范围n的$O(logn)$，对范围的要求很松。
二分可以递归或者循环实现，但递归要有不必要的性能消耗，所以要循环。
P1024 一元三次方程求解
一个是根在[-100,100]内，而且只要精确两位小数，范围是ok的。
三次函数连续，满足单调性。
而对于f(x)=0,x1< x2,f(x1)*f(x2)<0则x1,x2间必有一根这个结论可以快速验证答案的正确性。
于是二分答案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
double a,b,c,d;
bool vis[20005]={0};
inline double fx(double x){
return a*pow(x,3)+b*pow(x,2)+c*x+d;
}
void solve(double l,double r){
if(fx(l)*fx(r)>0)return;
int t=(r+100)*100;
if(fabs(l-r)<0.001){
if(!vis[t])
printf("%.2lf ",r);
vis[t]=1;
return;
}
double mid=(l+r)/2;
solve(l,mid);
solve(mid,r);
}
int main(){
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
for(int i=-100;i<100;i++)
solve(i,i+1);
return 0;
}
|
P1182 数列分段
此题使用了二分答案，就十分巧妙了。
二分的就是要求的答案，最大值的最小值，该答案一定不小于数列中的最大值（一个数一段），不大于该数列的和（只分一段），由题范围在$[0,10^9]$，可以二分求解。
最大值的最小值这个表述，是求满足某一条件后的最值，暗含了答案的单调性。
而此题的重点在如何快速判断猜的答案的正确性。因为数列分段是连续的几项，所以对于要验证的答案，只要以此为基准贪心，尽可能减少划的段数，如果大于要求就是答案太小；相反就是答案太大。
此验证方法是$O(n)$，加上二分总共是$O(nlog\sum{a_i})$，是ok的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=100005;
int n,m;
int a[MAXN]={0};
int ans;
bool judge(int mid){
int sum=0,num=1;
for(int i=1;i<=n;i++){
if(sum+a[i]>mid){
num++;
sum=0;
}
sum+=a[i];
}
if(num>m)return true;
return false;
}
int main(){
scanf("%d%d",&n,&m);
int l=0,r=0,mid;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
l=max(l,a[i]);
r+=a[i];
}
while(l<=r){
mid=(l+r)>>1;
if(judge(mid))l=mid+1;
else r=mid-1;
}
printf("%d",l);
return 0;
}
|