Educational Codeforces Round 60 (Rated for Div. 2)C. Magic Ship
链接:http://codeforces.com/problemset/problem/1117/C
来源:Codeforces
官方题解是二分天数,长知识了.重点就在于我们怎么判断二分到的那个天数是否符合我们的要求,我们先考虑这么多天如何我们不做任何操作只是让船跟着风飘,此时船必然会到达一个位置,当前的这个位置距离终点还有一段距离,此时我们可以通过让船动,看船在这么多天以内能否到达终点,如果可以那么就符合题意.一直二分就能找到最小的值.用数组来维护船的移动距离.
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<map>
#define pi 3.1415926
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int> Node;
typedef long long LL;
const int Max_n=100005;
int x,y,x2,y2,n,dx[Max_n],dy[Max_n];
char str[Max_n];
bool check(LL mid){//检查船能否在这个位置mid天走完
LL a=mid/n,b=mid%n;
LL tx=a*dx[n]+dx[b]+x;
LL ty=a*dy[n]+dy[b]+y;
LL ans=abs(x2-tx)+abs(y2-ty);
return ans<=mid;
}
int main(){
scanf("%d%d%d%d%d",&x,&y,&x2,&y2,&n);
scanf("%s",str);
for(int i=0;i<n;++i){
dy[i+1]=dy[i];
dx[i+1]=dx[i];
if(str[i]=='U') dy[i+1]++;//到达某个字符时,能够移动的距离
if(str[i]=='D') dy[i+1]--;
if(str[i]=='R') dx[i+1]++;
if(str[i]=='L') dx[i+1]--;
}
LL l=0,r=(LL)1e18,ans=-1;
while(l<=r){
LL mid=(l+r)>>1;
if(check(mid)){
r=mid-1;
ans=mid;
}else l=mid+1;
}
printf("%lld\n",ans);
return 0;
}