南阳理工OJ915解题报告

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

样例输出

4  

首先要解决的问题是如何判断有没有解。这个问题好解决，因为字符串长度相等，只要加减号的个数一致就行了，我们可以通过分别统计两个字符串加（减）号的个数，如果结果相等则有解，反之无解。

其次是怎样求最小移动次数，我们的贪心策略是从左到右遍历，当出现不一样的符号时我们寻找最近的可以使符号相同的字符的位置，找到后，该位置变成另一种符号（因为是从左到右，所以不用管开始的位置）

AC代码

#include<stdio.h>
#include<string.h>

const int maxn = 5000 + 10;
char s1[maxn], s2[maxn];
int n;

int find_min(int i)
{
    for(int j = i + 1; j < n; j++)
        if(s1[j] == s2[i]) return j;
    return -1;    //实际上并不会发生
}

int main()
{
    while(scanf("%s%s",s1,s2) == 2)
    {
        n = strlen(s1);

        //统计两个字符串中加号的个数
        int sum1,sum2;
        sum1 = sum2 = 0;
        for(int i = 0; i < n;i++)
        {
            if(s1[i] == '+') sum1++;
            if(s2[i] == '+') sum2++;
        }

        //判断并求解
        int count = 0;
        if(sum1 != sum2) printf("-1\n");
        else
        {
            for(int i = 0; i < n; i++)
            {
                if(s1[i] != s2[i])
                {
                    int pos = find_min(i);
                    s1[pos] = s1[i];
                    count += pos - i;
                }
            }
        }
        printf("%d\n",count);
    }
    return 0;
}