补题。
链接：点击打开链接
题意：一条线段，线段上有n个点，求出一个时间t，使得n个人在时间t内，可以同时到达某一个点。
二分写法：
二分时间t。
对于每一个t，我们有这样的结论：第x[i]个人能在t秒内到的范围是[Li, Ri] = [ x[i]-v[i]*t, x[i]+v[i]*t ]，对于一个解，必有max(Ri) >= min(Li)，即大家一定可以到达一段公共的线段。
对于一个成立的t，自然我们需要尝试求解更小的t，否则回到之前的mid值。
失误：const int eps = 1e-8; 导致死循环
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; const int MAXN = 60000 + 10; const double eps = 1e-7; int x[MAXN], v[MAXN], n; bool check(double t){ double ll=-1, rr=1e9+100; for(int i=0; i<n; ++i){ rr = min(rr, (double)(x[i]+v[i]*t)); ll = max(ll, (double)(x[i]-v[i]*t)); if(ll > rr) return false; } return true; } void solve(){ double l=0, r=1e9+5, mid; while(r-l>eps){ mid = (r+l)/2.0; if(check(mid)) r = mid; else l = mid; } printf("%.12lf\n", mid); } int main(){ scanf("%d", &n); for(int i=0; i<n; ++i) scanf("%d", &x[i]); for(int i=0; i<n; ++i) scanf("%d", &v[i]); solve(); return 0; }
明天补上三分的写法...
ss
