Walker

題意：

一個(gè)區(qū)間[0,n]，區(qū)間上有兩個(gè)點(diǎn)，坐標(biāo)分別是pos1，pos2，速度分別是v1，v2，這兩個(gè)點(diǎn)是在移動(dòng)，可以隨時(shí)改變移動(dòng)方向，問當(dāng)區(qū)間的每一塊均被一個(gè)點(diǎn)或兩個(gè)點(diǎn)移動(dòng)覆蓋時(shí)，最少花費(fèi)的時(shí)間是多少

題解：

介紹一個(gè)函數(shù)get_dis(pos,v,n)：在pos位置覆蓋區(qū)間n需要的最短時(shí)間
這個(gè)最短時(shí)間由兩個(gè)部分取最小值
一個(gè)部分是從pos走到0再返回到n
另一個(gè)是從pos走到n再返回到0
我們分類討論情況：

當(dāng)其中一點(diǎn)的速度>>另一點(diǎn)速度時(shí)，這樣我們就靠一個(gè)點(diǎn)來跑完全程就行

ans = min(ans , get_dis(p1,v1,n));ans = min(ans , get_dis(p2,v2,n));

當(dāng)兩個(gè)點(diǎn)一開始重合時(shí)，這樣可以分別往兩邊跑，取兩者時(shí)間最大值

ans = min(ans , max((n-p1)/v1 , p2/v2));

兩者相中間跑匯合后再反方向想往跑
我們著重講第三點(diǎn)，這個(gè)匯合點(diǎn)pos怎么確定？
我們先想想，在第三個(gè)情況下，兩者我們時(shí)間是要先取最大值，然后在最大值里選最小值，也就是兩者所用時(shí)間應(yīng)該越相近越好，這樣可以保證最大化的最小值合理，而確定pos我們當(dāng)然要用二分
當(dāng)前的mid使得前者時(shí)間大于后者時(shí)，mid就應(yīng)該往左移動(dòng)，所以r=mid，反之l=mid，進(jìn)行個(gè)100多次二分，這個(gè)答案就會(huì)非常精確了
以上三種情況取最小輸出

代碼：

#include <bits/stdc++.h> using namespace std;//在pos位置覆蓋到區(qū)間n需要的最短時(shí)間 double get_dis(double pos,double v,double n) { double a = (pos + n) / v; // 往左走到l再走到n double b = (n - pos + n) / v; //往右走到r再走到n return min(a,b); // 取最小值 }void Solve() {double n,p1,v1,p2,v2;scanf("%lf%lf%lf%lf%lf",&n,&p1,&v1,&p2,&v2);if(p1 > p2){swap(p1,p2);swap(v1,v2);}double ans = 9999999999999999;// 1.自己走完全程用的時(shí)間 ans = min(ans , get_dis(p1,v1,n));ans = min(ans , get_dis(p2,v2,n));// 2.相對(duì)走完自己的路程 ans = min(ans , max((n-p1)/v1 , p2/v2));// cout<<ans<<endl;double l = p1,r = p2; // 在p1和p2之間尋找一個(gè)分界點(diǎn) for(int i=1;i<=100;i++) // 二分分界點(diǎn) {double mid = (l + r) / 2; //分界點(diǎn) double ans1 = get_dis(p1,v1,mid); double ans2 = get_dis(n-p2,v2,n-mid);ans = min(ans,max(ans1,ans2));if(ans1 < ans2) l = mid; // 讓到達(dá)分界點(diǎn)的時(shí)間盡可能的相同 else r = mid;}printf("%.12f",ans); } int main() {int t;scanf("%d",&t);while(t--){Solve();if(t) puts("");} }/* 2 10000.0 1.0 0.001 9999.0 0.001 4306.063 4079.874 0.607 1033.423 0.847 */

總結(jié)

以上是生活随笔為你收集整理的Walker的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。