Codeforces Round #403 (Div. 2） B 二分 or 三分

题目链接

思路：
又在二分题上翻车了……

读完题一眼看出是一个二分题，但一开始选择了错误的对位置进行二分，后来发现错误后重新写了一个对时间进行二分，但忘了改二分的范围，然后一直过不了样例。
这算是一个很大的教训，做简单题不能急躁，Debug也一定要干净彻底。

此题可以可看成练习二分和三分，特别是搞清两种方法的差别和联系的一道很好的练习题。

对于本题，很明显，最佳的位置只有一个，在最佳位置左边或者右边都会使用时增大。故建立位置映射到时间的函数，图像可得：

故可进行三分。

而对于时间，一定存在某个最优解，在其左边的时间值都不能使所有人聚集在一起，而对于右边的时间值都能使所有人聚集在一起（即如果只需要两秒所有人就能聚集在一起，那么给三秒的时间，所有人也能聚集在一起）
故图像可得：

代码：

三分：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const double INF = 1e9;
const int A = 60000 + 100;

double x[A],v[A];
int n;

double check(double pos){
    double res = fabs(x[1] - pos) / v[1];
    for(int i=2 ;i<=n ;i++){
        res = max(res,fabs(x[i] - pos) / v[i]);
    }
    return res;
}

int main(){
    scanf("%d",&n);
    double l = INF,r = 0;
    for(int i=1 ;i<=n ;i++){
        scanf("%lf",&x[i]);
        l = min(l,x[i]),r = max(r,x[i]);
    }
    for(int i=1 ;i<=n ;i++){
        scanf("%lf",&v[i]);
    }

    double mid_1,mid_2;
    for(int i=1 ;i<=100 ;i++){
        mid_1 = (l*2 + r) / 3;
        mid_2 = (l + 2*r) / 3;
        //printf("l = %lf r = %lf\n",l,r);
        //printf("ans(mid_1) = %lf ans(mid_2) = %lf\n",check(mid_1),check(mid_2));
        if(check(mid_1) < check(mid_2)){
            r = mid_2;
        }
        else{
            l = mid_1;
        }
    }

    double pos = (mid_1 + mid_2)/2;
    printf("%.12f\n",check(pos));
    return 0;
}

二分：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const double INF = 1e9;
const int A = 60000 + 100;

double x[A],v[A];
int n;

bool check(double time){
    double Min = INF,Max = 0;
    for(int i=1 ;i<=n ;i++){
        Min = min(Min,x[i] + time*v[i]);
        Max = max(Max,x[i] - time*v[i]);
    }
    return Min >= Max;
}

int main(){
    scanf("%d",&n);
    for(int i=1 ;i<=n ;i++){
        scanf("%lf",&x[i]);
    }
    for(int i=1 ;i<=n ;i++){
        scanf("%lf",&v[i]);
    }

    double l = 0,r = INF;
    double mid;
    for(int i=1 ;i<=1000 ;i++){
        mid = (l + r) / 2;
        //printf("mid = %lf\n",mid);
        if(check(mid)){
            r = mid;
        }
        else{
            l = mid;
        }
    }

    printf("%.12f\n",mid);
    return 0;
}

注：
图片转自博客：算法录 之 二分和三分
侵删。