二分思维好题

发表于2021-10-20更新于2021-10-20阅读次数

Walker Gym - 102900D

题面：在一个长为n的线段，左端点为0，右端点为n

有两个端点分别位于p1,p2，它们的速度分别为v1,v2

问最少需要多少时间，可以使得p1，p2的路程覆盖整条线段
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
··

··

·
·
·

思路：
分类讨论：

先令p1<p2

①p1走完全程

②p2走完全程

③p1向右走完全部，p2向左走完全部

④p1走完左边的全部，p2走完右边的全部，剩余中间的部分p1与p2共同走完，二分中间相遇位置即可。

踩坑:最后二分出来的结果，没有取max(t1,t2)，只取了t1的值wa了。
原因是二分出来的最后结果，不能保证t1==t2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
* @Author: Marhoosh
* @Date:   2021-10-11 11:00:11
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-10-20 15:21:01
*/
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
const ll maxn=2e5+11;
ld x,x1,v1,x2,v2,ans;
void load(ld xx){
    ans=min(ans,xx);
}
void solve(){
    ld xx=min(x+x1,x-x1+x);
    load(xx/v1);//A走完全程
    xx=min(x+x-x2,x+x2);
    load(xx/v2);//B走完全程
    ld tt=max((x-x1)/v1,x2/v2);
    load(tt);//A,B对向走
    ld l=x1,r=x2;
    while(r-l>1e-12){
        ld mid=(l+r)/2;
        ld t1=min(x1+mid,mid+mid-x1)/v1;
        ld t2=min(x-mid+x2-mid,x-mid+x-x2)/v2;
        //load(max(t1,t2));
        if(t1<t2)  l=mid;
        else  r=mid;
    }
    ld t1=min(x1+l,l+l-x1)/v1;
    ld t2=min(x-l+x2-l,x-l+x-x2)/v2;
    load(max(t1,t2));
    printf("%.10LF\n",ans);
}
int main(){
    ll ca;cin>>ca;
    while(ca--){
        scanf("%Lf%Lf%Lf%Lf%Lf",&x,&x1,&v1,&x2,&v2);
        if(x1>x2){
            swap(x1,x2);swap(v1,v2);
        }
        ans=1e12;
        solve();
    }
    return 0;
}