首页 > 代码库 > SGU 170.Particles

SGU 170.Particles

Solution:

              这其实是道很简单的题。

              只要从一端开始,以‘+’或‘-’,任意一种开始找,找到与目标串最近的相同字符的距离就是需要交换的次数。

              +++———            对齐第一个‘-’                  —+++——

                                        ------------> 

              ———+++                                                ———+++

 

              以‘-’为例,不断向一端交换的话,最后交换的其实只要当前的‘-’和一个‘+’的位置,其他‘-’的相对位置不变。

              因此只要从左到右匹配第i个‘-’,计算出它们的距离差,累加即可。

 

code:

         

#include <iostream>#include <string>#define abs(x) (max(x,-(x)))using namespace std;const int INF = 5555;int  len, a[INF], b[INF], n1, n2, ans;string st;int main() {	cin >> st;	len = st.size();	for (int i = 0; i < len; i++)		if (st[i] == ‘-‘) a[++n1] = i;	cin >> st;	for (int i = 0, t = 0; i < len; i++)		if (st[i] == ‘-‘) b[++n2] = i;	if (n1 != n2) {		cout << -1;		return 0;	}	for (int i = 1; i <= n1; i++)		ans += abs (a[i] - b[i]);	cout << ans;}