CF1117C Magic Ship(二分)

对于自己控制和风向两种情况，我们可以发现，其实这两个是不冲突的

也就是对于风向我们是必须走的，而对于自己控制的肯定是朝最理想的状态

因此我们可以先把风向的贡献做出来，来二分天数，看看能否控制曼哈顿距离小于等于天数。

单调性的证明是，如果不可以满足条件，那么更小的天数也一定无法满足条件，因为我是最有利操作

假设我在之前某天存在答案，那么在之后，我一定可以至少抵消到负面影响。那么推到今天也是可以，但是今天不行，因此更小的天数也不行

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int dx[N],dy[N];
ll x1,y1,x2,y2;
int n;
bool check(ll mid){
    ll d=mid/n;
    ll last=mid%n;
    ll tmp=x1+d*dx[n]+dx[last];
    ll tmp2=y1+d*dy[n]+dy[last];
    if(abs(x2-tmp)+abs(y2-tmp2)<=mid)
        return true;
    else
        return false;
}
int main(){
    cin>>x1>>y1>>x2>>y2;
    string s;
    cin>>n;
    cin>>s;
    s=" "+s;
    int i;
    for(i=1;i<s.size();i++){
        dx[i]=dx[i-1];
        dy[i]=dy[i-1];
        if(s[i]=='D')
            dy[i]=dy[i]-1;
        else if(s[i]=='U'){
             dy[i]=dy[i]+1;
        }

        else if(s[i]=='L')
            dx[i]=dx[i]-1;
        else{
            dx[i]=dx[i]+1;
        }
    }
    ll r=1e18;
    ll l=1;
    int sign=0;
    while(l<r){
        ll mid=l+r>>1;
        if(check(mid)){
            r=mid;
            sign=1;
        }
        else
            l=mid+1;
    }
    if(!sign){
        cout<<-1<<endl;
    }
    else{
        cout<<l<<endl;
    }
}