AcWing 4217. 机器人移动

AcWing 4217. 机器人移动

#include#include#include#include#includeusing namespace std;typedef long long ll;const int N = 1e6 + 10;int n, m;string s;int sx[N], sy[N];int x, y;bool check (int len) { for (int i = 1; i + len - 1 <= n; i ++) { int j = i + len - 1; int nx = sx[n] - (sx[j] - sx[i - 1]); int ny = sy[n] - (sy[j] - sy[i - 1]); int d = abs(x - nx) + abs(y - ny); if (d <= len && (len - d) % 2 == 0) return 1; } return 0;}int main () { cin >> n >>s; s = " " + s; cin >> x >> y; for (int i = 1; i <= n; i ++) { sx[i] = sx[i - 1]; sy[i] = sy[i - 1]; if (s[i] == 'U') sy[i] ++; else if (s[i] == 'D') sy[i] --; else if (s[i] == 'L') sx[i] --; else sx[i] ++; } if (abs(x) + abs(y) > n || (n - abs(x) - abs(y)) % 2) puts("-1"); else { int l = 0, r = n; while (l < r) { int mid = l + r>> 1; if (check(mid)) r = mid; else l = mid + 1; } cout << l << endl; } return 0;}

考虑二分。 对于一个x，f[x] = 1, 对于正确答案ans, ans >= x，再小就不对了，所以具有二段性 这里最终能到达的点，是向量相加减之后的结果。对于多余的抵消点就行了。所以需要判断剩余的是否为偶数

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。