題意 ： 在一條橫線，n 個人， 每個有對應的速度，可以向兩邊走。問，這n個人到某點集合的最小時間。
枚據時間 time，則對i人能到的范圍為（x[i] + v[i]*time, x[i] - v[i]*time）。然后看所有人能到的范圍是否有交集。如果有交集 ，說明他們能在時間t內到某點集合。
#include <bits/stdc++.h>using namespace std;int x[70005],v[70005],n;bool canmeet(double time){ double left,right; for(int i=1;i<=n;i++) { if(i==1) { right = x[i] + v[i]*time; left = x[i] - v[i]*time; } else { double ri = x[i] + time*v[i]; double le = x[i] - time*v[i]; if( le > right || ri < left ) { return false; } left = max(le ,left); // 維持最大的左邊 值 right = min(right, ri); // 維持最小的右邊 值 } } return true;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",x+i); for(int i=1;i<=n;i++) scanf("%d",v+i); double l = 0, r = 1e9; while(r-l>1e-6) { double mid = (r+l)/2; if(canmeet(mid)) { r = mid; } else l = mid; }新聞熱點
疑難解答
