题意：
船在一个坐标，目的地在一个坐标，每天会有一个风向将船刮一个单位，船也可以移动一个单位或不动，问最少几天可以到目的地
思路：
二分天数，对于第k天
可以分解成船先被吹了k天，到达坐标（x1+sumx[k%n]+k/n*sumx[n], y1+sumy[k%n]+k/n*sumy[n]）
然后船在无风的情况下自己走k天是不是能到目的地就行了
注意二分的上限，如果能走到的情况下船可能每轮风只能移动一个有效单位，所以上限应该是1e9*1e5
代码：
#include<iostream> #include<cstdio> #include<algorithm> //#include<cmath> #include<cstring> #include<string> #include<stack> #include<queue> #include<deque> #include<set> #include<vector> #include<map> #include<functional> #define fst first #define sc second #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define lson l,mid,root<<1 #define rson mid+1,r,root<<1|1 #define lc root<<1 #define rc root<<1|1 #define lowbit(x) ((x)&(-x)) using namespace std; typedef double db; typedef long double ldb; typedef long long ll; typedef long long LL; typedef unsigned long long ull; typedef pair<int,int> PI; typedef pair<ll,ll> PLL; const db eps = 1e-6; const int mod = 998244353; const int maxn = 2e6+100; const int maxm = 2e6+100; const int inf = 0x3f3f3f3f; //const db pi = acos(-1.0); ll x1, x2; ll y1, y2; ll n; char a[maxn]; ll sumx[maxn]; ll sumy[maxn]; bool ck(ll k){ ll x = x1; ll y = y1; x += k/n*sumx[n] + sumx[k%n]; y += k/n*sumy[n] + sumy[k%n]; ll d = abs(x-x2)+abs(y-y2); if(d<=k)return true; return false; } int main() { scanf("%lld %lld", &x1,&y1); scanf("%lld %lld", &x2,&y2); scanf("%lld", &n); scanf("%s",a+1); ll l = 0, r = 1e15; for(int i = 1; i <= n; i++){ sumx[i] = sumx[i-1]; sumy[i] = sumy[i-1]; if(a[i]=='U'){ sumy[i]++; } if(a[i]=='D'){ sumy[i]--; } if(a[i]=='L'){ sumx[i]--; } if(a[i]=='R'){ sumx[i]++; } } ll ans = -1; while(l <= r){ ll mid = (l+r)/2; //printf("%lld %lld %lld\n", l, r, mid); if(ck(mid)){ r = mid-1; ans = mid; } else{ l = mid+1; } } printf("%lld", ans); return 0; } /* 10 59 -17 5 67 87 50 -71 54 27 -10 */