http://acm.nyist.net/JudgeOnline/problem.php?pid=915

+-字符串

時(shí)間限制：1000?ms ?|? 內(nèi)存限制：65535?KB難度：1描述

Shiva得到了兩個(gè)只有加號(hào)和減號(hào)的字符串，字串長度相同。Shiva一次可以把一個(gè)加號(hào)和它相鄰的減號(hào)交換。他想知道最少需要多少次操作才能把第一個(gè)字符串變換成第二個(gè)字符串。你現(xiàn)在要去幫助他完成那個(gè)這個(gè)問題。

輸入

多組測(cè)試數(shù)據(jù)

每組數(shù)據(jù)有兩行，每行包含一個(gè)由”+”和”-“最成的字符串。每個(gè)子符串長度不超過5000。

輸出

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

樣例輸入

++-+--+ ?

-++--++

樣例輸出

4

?

?解題思路：貪心，找到當(dāng)前不同的和離當(dāng)前最近的不同點(diǎn)，交換即可

?

?1?#include?<stdio.h>
?2?#include?<string.h>
?3?
?4?char?str1[5050],?str2[5050];
?5?
?6?int?main(){
?7?????int?len,?i,?j,?sum,?p1,?p2;
?8?????while(scanf("%s?%s",?str1,?str2)?!=?EOF){
?9?????????len?=?strlen(str1);
10?????????p1?=?p2?=?sum?=?0;
11?????????for(i?=?0;?i?<?len;?i++){
12?????????????if(str1[i]?==?'+'){
13?????????????????p1++;
14?????????????}
15?????????????if(str2[i]?==?'+'){
16?????????????????p2++;
17?????????????}
18?????????}
19?????????if(p1?!=?p2){
20?????????????printf("-1\n");
21?????????????continue;
22?????????}
23?????????for(i?=?0;?i?<?len;?i++){
24?????????????if(str1[i]?!=?str2[i]){
25?????????????????for(j?=?i?+?1;?j?<?len;?j++){
26?????????????????????if(str1[j]?==?str2[i]){
27?????????????????????????sum?+=?(j?-?i);
28?????????????????????????break;
29?????????????????????}
30?????????????????}
31?????????????????str1[j]?=?str1[i];
32?????????????}
33?????????}
34?????????printf("%d\n",?sum);
35?????}
36?????return?0;

37?}?

?

轉(zhuǎn)載于:https://www.cnblogs.com/angle-qqs/p/4085019.html

總結(jié)

以上是生活随笔為你收集整理的nyoj-915—— +-字符串的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。