二分时间，最左边的磁盘用最左边的指针去配对，并判断该指针在经过该磁盘的同时最多跑到最右边的位置，如果需要配对的磁盘在指针左边则有两种走法，第一种先向左走到磁盘位置再一直向右走，第二种先向右走然后向左走，正好在时间用完时停在磁盘处，判断两种情况哪种走的最右。如果磁盘在指针右边则一直向右走。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<cstring> #include<vector> #include<queue> #include<stack> #include<set> #include<map> #include<iomanip> #include<algorithm> #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define endl "\n" #define int long long using namespace std; const int INF = 1e18+5; const int maxn = 1e5+5; int a[maxn],b[maxn]; int m,n; bool check(int mid){ int t = 0; for( int i = 0 ;i < m ; ++i ){ if(a[i]+mid < b[t]){ continue; } if(a[i]-mid > b[t]){ return false; } int x; if(a[i] > b[t]) x = max( mid -a[i]+2*b[t],a[i]+(mid-a[i]+b[t])/2); else x = a[i]+mid; while(b[t] <= x && t < n) t++; if(t>=n){ return true; } } return false; } void solve(){ cin >> m >> n; for( int i = 0 ;i < m ; ++i ){ cin >> a[i]; } for( int i = 0 ; i < n ; ++i ){ cin >> b[i]; } int l = 0,r = INF;//左边界为0，右边界设置为1e18保证答案在范围内，该题要用long long while(l<r){ int mid = l+r >> 1; if(check(mid)) r = mid; else l = mid+1; } cout << l << endl; } main(){ IOS solve(); }
