Codeforces 782B：The Meeting Place Cannot Be Changed（三分搜索）

http://codeforces.com/contest/782/problem/B

题意：有n个人，每个人有一个位置和速度，现在要让这n个人都走到同一个位置，问最少需要的时间是多少。

思路：看上去很像二分搜索啊！枚举距离，判断是否有更少的时间，然后发现时间不随着距离单调增减，想起前两天被三分虐了一道题，那就是三分吧。

三分枚举距离，然后判断是否有更少的时间就可以了。比赛时候用了max函数还有精度开太大，超时了，索性直接循环100次。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define N 200010
 4 const double eps = 1e-9;
 5 double x[N], v[N], res;
 6 int n;
 7 
 8 double cal(double dis) {
 9     double ans = 0, tmp = 0;
10     for(int i = 1; i <= n; i++)
11         if(ans < fabs(x[i] - dis) / v[i]) ans = fabs(x[i] - dis) / v[i];
12     if(res > ans) res = ans;
13     return ans;
14 }
15 
16 int main() {
17     scanf("%d", &n);
18     double ma = 0, mi = 1000000000;
19     for(int i = 1; i <= n; i++) scanf("%lf", &x[i]), ma = max(ma, x[i]), mi = min(mi, x[i]);
20     for(int i = 1; i <= n; i++) scanf("%lf", &v[i]);
21     double l = mi, r = ma;
22     res = 1000000000;
23     for(int i = 0; i < 100; i++) {
24         double mid = (l + r) / 2;
25         double midd = (mid + r) / 2;
26         if(cal(mid) > cal(midd)) l = mid;
27         else r = midd;
28     }
29     printf("%.12f
", res);
30     return 0;
31 }