題意： n個人在南北路上，每個人都有自己的速度，最大不能超過vi，問最少需要多久能集合所有人。
思路：二分思想，每次判斷t在n個人中是否有相交的路程范圍。
#include <bits/stdc++.h>using namespace std;struct point{ double x,v;}p[100005];int n;int check(double t){ double a,b; for(int i = 0;i < n; i++) { double x = p[i].x - p[i].v*t; double y = p[i].x + p[i].v*t; if(i == 0) { a = x; b = y; } else { if(a > y || b < x) { return false; } if(a <= x) a = x; if(b >= y) b = y; } } return true;}int main(){ //freopen("in.txt","r",stdin); scanf("%d",&n); for(int i = 0;i < n; i++) { scanf("%lf",&p[i].x); } for(int i = 0;i < n; i++) { scanf("%lf",&p[i].v); } double ans = 0; double l = 0,m = 1e9,mid = m; while(m - l > 1e-7) { mid = (l+m)/2.0; if(check(mid)) { m = mid; ans = mid; } else { l = mid; } }新聞熱點
疑難解答
