题解:这道题可以.用二分来做,好吧,我根本想不到,太强了.
题意是给你起点和终点,还有循环出现的风向.船顺风行驶,走两格;逆风不动;与风成角度,斜着开,船自己不行驶会随风开.
这里的处理方法是:把随风行和船自己行驶分开.用dx[],dy[]计算风向循环节内的随风行的距离;最后对天数进行二分查找,因为不知道到底会行几天,所以我们先把右值先设置的大一点,
当在第x天时,船随风行到达的点与终点的曼哈顿距离(|x1-x2|+|y1-y2|)少于等于x,说明船时可以在x天内到达,那么r=mid-1;
否则,l=mid+1;
#include <iostream>
#include <cstdio>
#include <cmath>
const int N=1e5+5;
typedef long long ll;
using namespace std;
//char s[N];
int dx[N];
int dy[N];
char s[N];
int x1,yy,x2,y2,n;
bool check(ll x){
ll cx=x1+x/n*dx[n]+dx[x%n];
ll cy=yy+x/n*dy[n]+dy[x%n];
if((abs(x2-cx)+abs(y2-cy))<=x) return true;
return false;
}
int main()
{
scanf("%d%d%d%d",&x1,&yy,&x2,&y2);
scanf("%d",&n);
//cout<<"jjjj"<<endl;
//dx[0]=x1,dy[0]=yy;
scanf("%s",s+1);
for(int i=1;i<=n;i++){
//scanf("%s",s);
dx[i]=dx[i-1];dy[i]=dy[i-1];
//cout<<"fjjjj"<<endl;
switch(s[i]){
case 'U':dy[i]++;break;
case 'D':dy[i]--;break;
case 'L':dx[i]--;break;
case 'R':dx[i]++;break;
}
//cout<<"jjjj"<<endl;
}
//cout<<"hello"<<endl;
ll l=1,r=1e16;
ll ans=0;
while(l<=r){
ll mid=l+(r-l)/2;
if(check(mid)){
r=mid-1;
ans=mid;
}
else l=mid+1;
//cout<<l<<" "<<r<<endl;
}
if(ans==0){
printf("-1
");
return 0;
}
printf("%I64d
",ans);
//cout << "Hello world!" << endl;
return 0;
}