Description
坐标系上有一只小船,现在想从 $ (x_1,y_1) $ 去 $ (x_2,y_2) $。每时刻都有风,会把船往对应的风向吹一个单位(比如北风会把船往南吹),风是循环的,吹完 $ s_1 \sim s_n $ 就又会从 $ s_1 $ 开始。船在每一时刻都可以向指定方向移动一个单位。求船到目的地的最少时间,如果不能到达输出 -1。
Solution
容易证明关于总时间满足可二分性
判断时,加上 \([mid/n]\) 个周期偏移,加上 \(mid \bmod n\) 的单偏移后,检查曼哈顿距离是否不大于 \(mid\) 即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
int n,dx,dy;
char s[N];
int sx[N],sy[N];
signed main() {
ios::sync_with_stdio(false);
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2>>n>>s+1;
dx=x2-x1; dy=y2-y1;
for(int i=1;i<=n;i++) {
if(s[i]=='U') sx[i]=sx[i-1],sy[i]=sy[i-1]+1;
if(s[i]=='D') sx[i]=sx[i-1],sy[i]=sy[i-1]-1;
if(s[i]=='L') sx[i]=sx[i-1]-1,sy[i]=sy[i-1];
if(s[i]=='R') sx[i]=sx[i-1]+1,sy[i]=sy[i-1];
}
int l=0,r=1e16;
while(l<r) {
int mid=(l+r)/2;
if(abs(dx-sx[n]*(mid/n)-sx[mid%n]) + abs(dy-sy[n]*(mid/n)-sy[mid%n]) > mid) l=mid+1;
else r=mid;
}
cout<<(r>1e15?-1:r);
}