撰写https://blog.csdn.net/u012469987/article/details/50897291
二分法
经常有这样的问题，求xxx最小值的最大值，即求符合条件的值里的最大值，这种问题有个解法叫二分答案法。一听，什么，不知道的答案也能二分？嗯没错，关键在于这个答案是可以判断是不是符合条件的。
算法思想
以求最小值的最大值（最小值最大化）为例，尝试一个可能的答案，如果这个答案符合题目条件，那么它肯定是“最小”（可行解），但不一定是“最大”（最优解），然后我们换个更大的可能答案，如果也符合条件，那这个新可行解就更优，不断重复即可。怎么找呢？这时就该二分上场了。
二分前提
1.答案区间上下限确定，即最终答案在哪个范围是容易知道的。
2.检验某值是否可行是个简单活，即给你个值，你能很容易的判断是不是符合题目要求。
3.可行解满足区间单调性，即若x是可行解，则在答案区间内x+1（也可能是x-1）也可行。
两种情况
下图中L,R为当前答案区间，M为中心点，根据二分思想判断M是否符合条件，再移动L或R，变成L’，R’，图中的T和F表示是否符合条件。
1.最小值最大化
int l = min_ans, r = max_ans;
while (l < r) {
int mid = (l + r + 1) / 2; //+1避免 r == l + 1 时mid一直等于l，从而死循环
if (ok(mid)) //符合条件返回True
l = mid;
else
r = mid - 1;
}
希望答案尽可能大，所以我们需要确保左区间L点符合题目条件（最小），至于R是否符合条件是不确定的，首先判断M点符合与否，符合则将L移到M点，维持了L的True属性，也增大了所要的最小值所在区间，如果不符合，没办法在保持L的True属性情况下移动L，那就移动R。
2.最大值最小化
int l = min_ans, r = max_ans;
while (l < r) {
int mid = (l + r) / 2;
if (ok(mid)) //符合条件返回True
r = mid;
else
l = mid + 1;
}
按同样道理分析，维持R的True属性即可。这里的mid就不需要加1了，因为 mid 跟 l 重合时，l = mid + 1;会自增，而当 mid 和 r 重合时 l 也跟 r 重合，结束循环了。
注意点
1. 每次循环都要确保L和R有一个被更新，否则死循环就呵呵了。
2. 答案是浮点数的情况：区间更新不能加1，这样变动太大，直接
l = mid; r = mid;
三分法
当二分的函数值不是递增/减，而是先增后减或者先减后增时二分就挂了。此时需要三分法，这里直接盗用hihocoder Problem 1142的图
如图这种情况先减后增有极小，若lm比rm低（即lm对应的函数值 < rm函数值）则极小点（图中最低点）肯定在[ left, rm ] ，反之在[ lm, right ]，剩下就跟二分一样根据大小关系调整区间就行了。
那lm和rm取值多少？一个不错的取值是lm为整个区间的1/3点，rm为2/3点，即 lmid = l + (r – l)/3; rmid = r – (r – l)/3;
嗯三分就这样完了。
然后另外一种情况，先增后减有极大：
如图lm低于rm，则极大在[ lm,right ]（为啥不是[ left, rm ]？你试试把rm放在lm右边，极大值左边看看？），否则极大在 [ left, rm ]。写代码上就是极小的处理语句反过来就行了。
HDU 2899 Strange fuction 给一函数，该函数在任意Y>0的情况下x在[0,100]内有极小值，求之。
按思路套上代码即可AC
#include
#include
#include
using namespace std;
double y;
double val(double x){
return 6*x*x*x*x*x*x*x+8*x*x*x*x*x*x+7*x*x*x+5*x*x-y*x;
}
double solve(double l,double r){
double eps = 1e-7;
while(l + eps < r){
double lmid = l + (r-l)/3,rmid = r - (r-l)/3;
if(val(lmid) < val(rmid)){ r = rmid; }else{ l = lmid; } } return val(l); } int main(){ int t; cin>>t;
while(t--){
cin>>y;
printf("%.4f\n", solve(0,100.0));
}
return 0;
}
hihocoder 1142
有一条抛物线y=ax^2+bx+c和一个点P(x,y)，求点P到抛物线的最短距离d。
输入
第1行：5个整数a,b,c,x,y。前三个数构成抛物线的参数，后两个数x,y表示P点坐标。-200≤a,b,c,x,y≤200
输出
第1行：1个实数d，保留3位小数(四舍五入)
样例输入
2 8 2 -2 6
样例输出
2.437
hiho的数据只有一组a>0的情况，所以下面代码直接过。
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define clr( a , x ) memset ( a , x , sizeof (a) );
#define RE freopen("1.in","r",stdin);
#define WE freopen("1.out","w",stdout);
#define SpeedUp std::cout.sync_with_stdio(false);
const int maxn = 1e5+5;
const int inf = 0x3f3f3f3f;
double a,b,c,x,y;
double val(double X){
return sqrt((X-x)*(X-x)+(a*X*X+b*X+c-y)*(a*X*X+b*X+c-y));
}
double solve(double l,double r){
double eps = 1e-5;
while(l+eps<r){
double lmid = l + (r-l)/3,rmid = r - (r-l)/3;
if(val(lmid) < val(rmid)){ r = rmid; }else{ l = lmid; } } return val(l); } int main(){ // RE while(cin>>a>>b>>c>>x>>y){
printf("%.3f\n", solve(-200.0,200.0));
}
return 0;
}