codeforces 712B. Memory and Trident

时间:2021-06-22 06:22:48

题目链接:http://codeforces.com/problemset/problem/712/B

题目大意:

  给出一个字符串(由'U''D''L''R'),分别是向上、向下、向左、向右一个单位,问修改若干字符,可以回到原点。回不到原点输出 -1,可以则输出最少修改的步数。

解题思路:

  如果是奇数步,则不可以回到原点 直接输出-1;

  否则:分别统计出向各个方向的步数,求出 abs(U-D)+abs(L-R) 回不到原点多余的步数。然后让 剩余的步数/2 修改一处可以保证两个状态OK.(例如:DRUR=>DRUL,修改了最后一个R为L,不仅保证了RL,而且取消了了本身对应的L,故修改一处即可)。

AC Code:

 #include<bits/stdc++.h>
using namespace std; int main()
{
string s;
int a[];
while(cin>>s)
{
memset(a,,sizeof(a));
for(int i=; i<s.size(); i++)
{
if(s[i]=='L')a[]++;
if(s[i]=='R')a[]++;
if(s[i]=='U')a[]++;
if(s[i]=='D')a[]++;
}
if(s.size()%)
printf("-1\n");
else printf("%d\n",(abs(a[]-a[])+abs(a[]-a[]))/);
}
return ;
}