当前位置:首页 > 贪心 > 正文
SSOJ1350+-字符串
182+

题目大意:两个长度相同的有加号和减号组成的字符串,能否通过交换相邻字符,让他们变成同一个字符串?如果可以,至少需要交换多少次?

题目描述

Shiva得到了两个只有加号和减号的字符串,字串长度相同。Shiva一次可以把一个加号和它相邻的减号交换。他想知道最少需要多少次操作才能把第一个字符串变换成第二个字符串。你现在要去帮助他完成那个这个问题。

输入

多组测试数据

每组数据有两行,每行包含一个由”+”和”-“最成的字符串。每个子符串长度不超过5000。

输出

仅一个整数,输出最少需要操作的次数。如果答案不存在,输出-1。

样例输入

++-+--+
-++--++

样例输出

4

解题思路

长度相同,如果加号数量相同,或者减号数量相同,那么可以交换得到同一个字符串,否则不行。

两个字符串a和b,a交换后变成b,或者b交换后变成a,交换次数是相同的,只是方向可能相反而已。不妨设a交换字符变成b,结果是a的所有加号的位置跟b一样,所有减号的位置跟b也一样。这样实际上就是a的第一个加号跟b的第一个加号对应,第二个、第三个等也是一一对应起来的。我们只需要把其中一种符号的各个对应位置交换到一起的次数累加起来即可,因为另外一个符号会自动对齐。

程序实现

更多

About

坚决不Copy代码!

本文标签:,

SSOJ1350+-字符串:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter