首页 > 代码库 > Codeforces 712B. Memory and Trident
Codeforces 712B. Memory and Trident
题目链接:http://codeforces.com/problemset/problem/712/B
题意:
一个人站在坐标原点处,他可以往上(U), 下(D), 左(L), 右(R), 四个方向移动,现给你一个移动序列,为了使他最后仍然能回到原点,你需要对这个序列做一些改变,每次可以改变其中一个字母,问最少的改变次数.
思路:
如果这个序列的长度是奇数,那么肯定不可能回到原点,则直接输出“-1”, 否则可以这么想, 如果 “U” 与 “ D” 和 “L” 与 “R” 能成对出现(和出现次序无关), 那么肯定可以回到原点,所以这里需要做的就是分别统计这四个操作出现的次数, 水平方向相减, 竖直方向相减, 意味着去掉成对出现的对数. 如果结果不为 0 ，那么就需要做出改变,可以想到, 对相减后的差值除 2 就可以得到最少的改变次数.
代码:
#include <bits/stdc++.h>using namespace std;typedef long long LL;const int MAXN = 100000;int main() { //freopen("input", "r", stdin); ios_base::sync_with_stdio(); cin.tie(); char s[MAXN + 3], c; int len = 0; while( (c = getchar()) != ‘\n‘ ) s[len++] = c; map <char, int> mp; mp[‘U‘] = mp[‘D‘] = mp[‘L‘] = mp[‘R‘] = 0; for(int i = 0; i < len; i++) mp[s[i]] ++; //统计每个操作出现的次数 int lr = abs(mp[‘L‘] - mp[‘R‘]), du = abs(mp[‘D‘] - mp[‘U‘]); if(len & 1) cout << "-1" << endl; else cout << ( (lr + du) >> 1 ) << endl; return 0;}
Codeforces 712B. Memory and Trident
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。