题目描述：
在一个无限大的二维平面上有一个机器人。
初始时，机器人位于点 $ (0,0) $ 。
机器人可以执行四种行动指令：
U — 从 $ (x,y) $ 移动到 $ (x,y+1) $ ；D — 从 $ (x,y) $ 移动到 $ (x,y−1) $ ；L — 从 $ (x,y) $ 移动到 $ (x−1,y) $ ；R — 从 $ (x,y) $ 移动到 $ (x+1,y) $ 。
给定一个长度为 $ n $ 的指令序列，指令编号 $ 1 \sim n $ ，机器人将按顺序依次执行序列中的每个行动指令。
我们希望机器人最终抵达目标地点 $ (a,b) $ 。
为了达成这一目的，我们可能需要对指令序列进行修改。
每次修改可以选择其中一个指令，并将其替换为四种指令之一。
注意，只能对序列中的指令进行替换，不得随意删除指令或添加额外指令。
不妨设经过修改的指令中，编号最小的指令编号为 minID，编号最大的指令编号为 maxID。
我们定义修改成本为 $ \text{maxID}−\text{minID}+1 $ 。
例如，将 RRRRRRR 修改为 RLRRLRL，则编号为 $ 2,5,7 $ 的指令经过了修改，修改成本为 $ 7−2+1=6 $ 。
请你计算，为了使得机器人能够最终抵达目标点 $ (a,b) $ ，所需花费的最小修改成本。
如果不需要对序列进行修改，则成本为 0。
输入格式
第一行包含整数 n。
第二行包含一个长度为 n 的字符串，表示指令序列，字符串中只包含 U，D，L，R。
第三行包含两个整数 a,b，表示机器人的目标位置为 $ (a,b) $ 。
输出格式
输出一个整数，表示最小修改成本。
如果无论如何修改，机器人都无法抵达目标位置，则输出 −1。
数据范围
前四个测试点满足 $ 1 \le n \le 10 $ 。
所有测试点满足 $ 1 \le n \le 2×10^5，−10^9 \le x,y \le 10^9 $ 。
输入样例1：
输出样例1：
输入样例2：
输出样例2：
输入样例3：
输出样例3：
题解：
代价的定义为 $ \text{maxID}−\text{minID}+1 $ ，可以发现是一个区间 $ [minID, maxID] $ ，只需要对这个区间中的指令进行修改。显然满足二分性。二分区间的长度，枚举每一个区间，注意如何进行 check mid。
此外，把每次移动都看作向量的加减，那么只需要记录两个方向轴的单位向量就行。可以使用前缀和，得到 $ [0, minID - 1], [maxID + 1, n - 1] $ 里面的 $ x,y $ 方向的数量，和终点坐标就行对比，看看需要改变多少，记为 $ need $ ，需要满足 mid >= need，而且二者需要保持相同的奇偶性，因为相差为奇数时无法通过抵消满足。
代码：
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 2e5 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
PII a[maxn];
string s;
int ex, ey;
bool check(int mid)
{
if (mid > n)
return false;
int sx, sy, need;
for (int i = 1; i <= n - mid + 1; i++)
{
sx = a[i - 1].first + a[n].first - a[i + mid - 1].first;
sy = a[i - 1].second + a[n].second - a[i + mid - 1].second;
need = abs(sx - ex) + abs(sy - ey);
if (need <= mid && (mid - need) % 2 == 0)
{
return true;
}
}
return false;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
cin >> s;
cin >> ex >> ey;
for (int i = 1; i <= s.length(); i++)
{
a[i].first = a[i].second = 0;
if (s[i - 1] == 'R')
{
a[i].first = 1;
}
else if (s[i - 1] == 'L')
{
a[i].first = -1;
}
else if (s[i - 1] == 'U')
{
a[i].second = 1;
}
else
{
a[i].second = -1;
}
}
for (int i = 1; i <= n; i++)
{
a[i].first += a[i - 1].first;
a[i].second += a[i - 1].second;
}
int l = 0, r = n;
int ans = -1;
while (l <= r)
{
int mid = (l + r) >> 1;
if (check(mid))
{
ans = mid;
r = mid - 1;
}
else
{
l = mid + 1;
}
}
cout << ans << endl;
return 0;
}
|