<题目链接>
题目大意：
给定起点和终点，某艘船想从起点走到终点，但是海面上会周期性的刮风，船在任何时候都能够向四个方向走，或者选择不走，船的真正行走路线是船的行走和风的走向叠加的，求船从起点到终点的最小步数。
解题分析：
因为本题数据量十分大，并且船和风叠加的行走路线比较复杂，所以我们考虑用二分答案解题。因为从起点到终点的有效步数是一定的，所以我们可以将船走动的总步数与风的步数(风吹不动的船的步数)分别进行计算，因为风是周期性吹的，但是从起点走到终点不一定是整数个周期，所以我们需要记录每个周期任意时间点所行走的路程前缀。
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
#define N int(1e5+7)
char s[N];
ll n,sx,sy,ex,ey,nx,ny;
ll dx[N],dy[N]; bool check(ll step){ //枚举的总步数
ll xx=dx[n]*(step/n)+dx[step%n]; //风所移动的距离
ll yy=dy[n]*(step/n)+dy[step%n];
return step>=abs(nx-xx)+abs(ny-yy);
}
int main(){
scanf("%lld%lld%lld%lld",&sx,&sy,&ex,&ey);
nx=ex-sx;ny=ey-sy;
scanf("%d%s",&n,s+);
for(int i=;i<=n;i++){
dx[i]=dx[i-],dy[i]=dy[i-];
if(s[i]=='U') dy[i]++; //风在竖直方向上的移动
if(s[i]=='D') dy[i]--;
if(s[i]=='L') dx[i]--; //风在水平方向上的移动
if(s[i]=='R') dx[i]++;
}//得到周期内竖直和水平方向的前缀位移
ll l=,r=1e18,ans=-; //二分答案，二分步数
while(l<=r){
ll mid=l+r>>;
if(check(mid))ans=mid,r=mid-;
else l=mid+;
}
printf("%lld\n",ans);
}
2019-02-20