题目:题目链接

思路:对于x方向距离与y方向距离之和大于n的情况是肯定不能到达的,另外,如果n比abs(x) + abs(y)大,那么我们总可以用UD或者LR来抵消多余的大小,所以只要abs(x) + abs(y) <= n && (n - abs(x) + abs(y)) % 2 == 0,就一定可以到达终点,判断完之后二分答案长度就可以了

AC代码:

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <list>
#include <cstdlib>
#include <cmath> #define FRER() freopen("in.txt", "r", stdin)
#define FREO() freopen("out.txt", "w", stdout)
#define INF 0x3f3f3f3f using namespace std; const int maxn = + ; int n, cx[maxn], cy[maxn], x, y;
char str[maxn]; bool judge(int t) {
for(int i = t; i <= n; ++i) {
int lx = cx[n] - cx[i] + cx[i - t];
int ly = cy[n] - cy[i] + cy[i - t];
if (abs(x - lx) + abs(y - ly) <= t)
return true;
}
return false;
} int main()
{
cin >> n >> str >> x >> y;
if(abs(x) + abs(y) > n || (abs(x) + abs(y)) % != n % ) {
cout << - << endl;
}
else {
for(int i = ; i < n; ++i) {
if(str[i] == 'U') cx[i + ] = cx[i], cy[i + ] = cy[i] + ;
else if(str[i] == 'D') cx[i + ] = cx[i], cy[i + ] = cy[i] - ;
else if(str[i] == 'L') cx[i + ] = cx[i] - , cy[i + ] = cy[i];
else if(str[i] == 'R') cx[i + ] = cx[i] + , cy[i + ] = cy[i];
}
int l = , r = n;
while(l < r) {
int m = (l + r) >> ;
if(judge(m))
r = m;
else
l = m + ;
}
cout << r << endl;
}
return ;
}

最新文章

  1. IE浏览器下异步请求的缓存问题
  2. Linux快速入门02-文件系统管理
  3. header的安全配置指南
  4. Ubuntu 针对 SSD 的优化方案
  5. Oracle异常处理,动态游标
  6. Dropping water balloons
  7. OS X: Keyboard shortcuts
  8. call-template和apply-templates
  9. Linux命令 查看文件内容
  10. Kotlin + Spring Boot 请求参数验证
  11. .NET Core实战项目之CMS 第十五章 各层联动工作实现增删改查业务
  12. Java 异常: SimpleDateFormat java.lang.NumberFormatException: multiple points
  13. mysql初次启动相关配置
  14. 四、触发器(Trigger)
  15. Error:fatal: Not a git repository (or any of the parent directories): .git
  16. JavaScript深入解读
  17. mongo源码学习(四)invariant
  18. Python os.chmod
  19. 创芯Xilinx Microblaze 学习系列第一集
  20. bzoj4518: [Sdoi2016]征途(DP+决策单调性分治优化)

热门文章

  1. NET Core项目
  2. 获取jar包当前的路径
  3. 前端js编码
  4. 《从0到1学习Flink》—— 如何自定义 Data Sink ?
  5. java获取服务器一些信息的方法
  6. 第一课:K线
  7. dao层写展示自己需要注意的问题
  8. 不小心踩到的XMAPP的N种问题
  9. ssh免密登录配置方法
  10. 理解Postgres性能