【二分答案】【数学思维】codeforces1117C Magic Ship_u', 'd', 'l', 'r' 二分答案

C. Magic Ship
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You a captain of a ship. Initially you are standing in a point (x1,y1) (obviously, all positions in the sea can be described by cartesian plane) and you want to travel to a point (x2,y2).

You know the weather forecast — the string s of length n, consisting only of letters U, D, L and R. The letter corresponds to a direction of wind. Moreover, the forecast is periodic, e.g. the first day wind blows to the side s1, the second day — s2, the n-th day — sn and (n+1)-th day — s1 again and so on.

Ship coordinates change the following way:

if wind blows the direction U, then the ship moves from (x,y) to (x,y+1);
if wind blows the direction D, then the ship moves from (x,y) to (x,y−1);
if wind blows the direction L, then the ship moves from (x,y) to (x−1,y);
if wind blows the direction R, then the ship moves from (x,y) to (x+1,y).
The ship can also either go one of the four directions or stay in place each day. If it goes then it’s exactly 1 unit of distance. Transpositions of the ship and the wind add up. If the ship stays in place, then only the direction of wind counts. For example, if wind blows the direction U and the ship moves the direction L, then from point (x,y) it will move to the point (x−1,y+1), and if it goes the direction U, then it will move to the point (x,y+2).

You task is to determine the minimal number of days required for the ship to reach the point (x2,y2).

Input
The first line contains two integers x1,y1 (0≤x1,y1≤109) — the initial coordinates of the ship.

The second line contains two integers x2,y2 (0≤x2,y2≤109) — the coordinates of the destination point.

It is guaranteed that the initial coordinates and destination point coordinates are different.

The third line contains a single integer n (1≤n≤105) — the length of the string s.

The fourth line contains the string s itself, consisting only of letters U, D, L and R.

Output
The only line should contain the minimal number of days required for the ship to reach the point (x2,y2).

If it’s impossible then print “-1”.

---

 很好的一道题，题意很简明。比赛时心里一直在想是不是二分答案，开始感觉不想然后有往其它地方想，后来仔细感受了一下，似乎确实是满足二分性质的，于是当时匆匆写了下。
 实际上，可以发现，四个方向的前进对于船和目的地的相对曼哈顿距离只有两个贡献，增加1或者减少1。由于船只可以选择停止，所以，要到达目的地的话，船行进的时间是小于或等于承受风的时间的，绝对不能大于。将风的作用和船的行进分开来看待，首先风刮过时间T，使得相对曼哈顿距离为S，然后船在T时间最多使得距离缩小T，所以T>=S。
 绘制图像， 横轴为时间，纵轴为距离，第一条是直线y=T，第二条是y=S，这是一条起点为非负数，斜率的绝对值为1的折线。很容易发现如果两者在一处相交，必然在此之后都有T>=S满足，所以，如果在时间T船可以到达目的地，那么在之后的任何时间都可以到目的地。于是可以做二分答案。
 这种思路也可以限定出答案的范围，起始距离最多为2E9，如果到达，每n步至少要靠近一次，也就是距离缩短2，由于n<=1E5，所以可以求出二分的上限是1E14。（妈呀其实当时写二分的时候哪里想了这么多，凑巧就写了个1E14，再小一点就要被hack掉了QwQ）

#include<cstdio>
#include<algorithm>
using namespace std;
using LL=long long;

LL L,R=1E14,x,y,x1[100005],y1[100005];
int n;
char s[100005];

bool check(LL m)
{
	LL p=m/n*x1[n],q=m/n*y1[n];
	p+=x1[m%n],q+=y1[m%n];
	return abs(x-p)+abs(y-q)<=m;
}

int main()
{
	scanf("%lld%lld%lld%lld%d%s",&x1[0],&y1[0],&x,&y,&n,s+1);
	x-=x1[0],y-=y1[0];
	x1[0]=y1[0]=0;
	for(int i=1;i<=n;i++)
	{
		x1[i]=x1[i-1],y1[i]=y1[i-1];
		if(s[i]=='U')
			y1[i]++;
		else if(s[i]=='D')
			y1[i]--;
		else if(s[i]=='L')
			x1[i]--;
		else
			x1[i]++;
	}
	while(L<R)
	{
		LL M=L+R>>1;
		if(check(M))
			R=M;
		else
			L=M+1;
	}
	if(!check(L))
		printf("-1");
	else
		printf("%lld",L);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

 实际上如果你想到了作图这一步，不用二分答案也能求了。因为两个曲线的纵坐标之差是一个周期变化一个定值，所以直接做一个除法是可以求出相交是在哪个周期中，接着枚举具体是在哪一步。