nyoj 915 +-字元串

+-字元串

時間限制： 1000 ms  |            記憶體限制： 65535 KB 難度： 1

描述

Shiva得到了兩個隻有加号和減号的字元串，字串長度相同。Shiva一次可以把一個加号和它相鄰的減号交換。他想知道最少需要多少次操作才能把第一個字元串變換成第二個字元串。你現在要去幫助他完成那個這個問題。

輸入

多組測試資料

每組資料有兩行，每行包含一個由”+”和”-“最成的字元串。每個子符串長度不超過5000。

輸出

僅一個整數，輸出最少需要操作的次數。如果答案不存在，輸出-1。

樣例輸入

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

樣例輸出

4      

第一種思路：（好想的思路）比較兩個字元串a,b-->找到不同的字元（即a[i]!=b[i]），并從該字元後一項j=i+1開始尋找能與字元a[i]交換的字元（需要滿足a[j]==b[i]）。當然在找a[j]的過程中，操作次數min是随着j的一次次增大而增大，直到找到a[j]跳出，進行下一次循環...代碼如下：      

#include<stdio.h>
#include<string.h>
int main()
{
    int n,i,j;
    int l1,l2;
    int c,d;
    int min;//需要的最少次數 
    char a[5010],b[010];
    while(scanf("%s %s",&a,&b)!=EOF)
    {
        l1=strlen(a);
        l2=strlen(b);
        /*判斷兩個字元串是否可以互相變換*/
        c=d=0;
        for(i=0;i<l1;i++)
        {
            if(a[i]=='+')
            c++;
        }
        for(i=0;i<l2;i++)
        {
            if(b[i]=='+')
            d++;
        }
        if(c!=d||l1!=l2)
        printf("-1\n");
        else
        {
            min=0;
            for(i=0;i<l1;i++)
            {
                /*好好體會*/
                if(a[i]!=b[i]) 
                {
                    for(j=i+1;j<l1;j++)
                    {
                        min++;
                        if(a[j]==b[i])
                        {
                            a[j]=a[i];//很關鍵 
                            break;
                        }
                    }
                }
            }
            printf("%d\n",min);
        }
    }
    return 0;
}
           
   

思路二：用兩個數組分别記錄兩個字元串中+（或-）的位置，可以知道的是，這兩個數組長度len是一樣的。然後隻需從0->len依次算出兩個數組中相鄰+的位置差的絕對值，最後相加即可。      

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
    int a1[5010],b1[5010];//記錄+位置數組
    char a[5010],b[5010];
    int i,j,l1,l2;
    int c,d;
    int min;//最少變換次數 
    while(scanf("%s %s",&a,&b)!=EOF)
    {
        l1=strlen(a);
        l2=strlen(b);
        c=d=0;
        for(i=0;i<l1;i++)
        {
            if(a[i]=='+')
            {
                a1[c++]=i;
            }
        }
        for(j=0;j<l2;j++)
        {
            if(b[j]=='+')
            {
                b1[d++]=j;
            }
        }
        if(c!=d||l1!=l2)
        printf("-1\n");
        else
        {
            min=0;
            for(i=0;i<c;i++)
            {
                min+=abs(a1[i]-b1[i]);
            }
            printf("%d\n",min);
        }
    } 
    return 0;
}