【链接】 我是链接,点我呀:)
【题意】
题意
【题解】
我们可以把这个行船的过程分解成两个过程
1.船经过时间t被风吹到了某个地方
2.船用这t时间尝试到达终点(x2,y2)
会发现如果时间t能最终能到达(x2,y2)的话
对于任意的时间t1>t,t1也能到达。
因为对于t后面的时间,比如t+1,那么风最多把船往偏离终点x,y的方向吹了一下,这一下总是能让多出来的时间(1单位时间)补回来的。
那么t-(船被吹了之后的位置与(x2,y2)的曼哈顿距离)肯定会随着t的增大而不下降。所以总是能到达的
所以它总是有一个下界的时间t1的。
我们只要二分这个时间t1就好
按照上面的思路,二分,然后判断船被吹了以后,能否到达(x2,y2),如果不能到就增加时间
【代码】
#include <bits/stdc++.h>
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i>= b;i--)
#define ll long long
using namespace std;
const int N = 1e5;
ll x1,y1,x2,y2,n;
ll pre[N+10][2];
string s;
ll get_mhd(ll x1,ll y1,ll x2,ll y2){
return abs(x1-x2)+abs(y1-y2);
}
bool ok(ll t){
ll xx = t/n*pre[n][0] + pre[(long long)t%n][0];
ll yy = t/n*pre[n][1] + pre[(long long)t%n][1];
ll tx = x1 + xx,ty = y1 + yy;
ll temp = get_mhd(tx,ty,x2,y2);
if (temp<=t) return true;
return false;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin >> x1 >> y1 >> x2 >> y2;
cin >> n;
cin >> s;
rep1(i,0,(int)s.size()-1){
rep1(j,0,1) pre[i+1][j] = pre[i][j];
if (s[i]=='U'){
pre[i+1][1]++;
}
if (s[i]=='D'){
pre[i+1][1]--;
}
if (s[i]=='L'){
pre[i+1][0]--;
}
if (s[i]=='R'){
pre[i+1][0]++;
}
}
ll l = 1,r = 2e14,temp = -1;
while (l<=r){
ll mid = (l+r)>>1;
if (ok(mid)){
temp = mid;
r = mid - 1;
}else l = mid + 1;
}
cout<<temp<<endl;
return 0;
}