http://nyoj.top/problem/915

  • 内存限制:64MB 时间限制:1000ms

题目描述:

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

输入描述:

多组测试数据

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

输出描述:

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

样例输入:

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

样例输出:

4

解题思路:

首先，字符串a,b的长度必须一致，否则return -1，然后就是字符串a,b的’+’个数必须一致，否则return -1。当以上条件满足时，就可以正式的比较a,b了。b的第一个’+’最后一定和a的第一个’+’匹配 ， … … ，b的第i个’+’最后一定a的第i个’+’匹配 .因为是次数最少，那么a的第一个’+’离得最近的一定是b的第一个’+’ ， 总不能够南辕北辙，把b的第2个加好拿去和a的第一个加号去比。那么我们让a不动，移动b的加号，且我们已经知道b的加号要移动到哪个位置。只需用 i 下标表示a的第k个加号，用 j 下标表示b的第k个加号，然后移动的距离就是 abs(j-i) .

#include <iostream>
#include <algorithm>
using namespace std;
int num(string a)
{
    int ans = 0;
    for (int i = 0; i < a.length(); i++)
        if (!(a[i] - '+'))
            ans++;
    return ans;
}
int main()
{
    string stra, strb;
    int t, j, ans, lena, lenb;
    while (cin >> stra >> strb)
    {
        j = ans = 0;
        lena = stra.length();
        lenb = strb.length();
        if (lena != lenb || num(stra) != num(strb))
        {
            puts("-1");
            continue;
        }
        for (int i = 0; i < lena; i++)
        {
            if (!(stra[i] - '+'))
            {
                while (j < lenb)
                {
                    j++;
                    if (!(strb[j - 1] - '+'))
                    {
                        ans += abs(i - j + 1);
                        break;
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}