首页 > 代码库 > nyoj-915—— +-字符串
nyoj-915—— +-字符串
http://acm.nyist.net/JudgeOnline/problem.php?pid=915
+-字符串
时间限制：1000 ms | 内存限制：65535 KB
难度：1
- 描述
- Shiva得到了两个只有加号和减号的字符串，字串长度相同。Shiva一次可以把一个加号和它相邻的减号交换。他想知道最少需要多少次操作才能把第一个字符串变换成第二个字符串。你现在要去帮助他完成那个这个问题。
- 输入
- 多组测试数据
每组数据有两行，每行包含一个由”+”和”-“最成的字符串。每个子符串长度不超过5000。 - 输出
- 仅一个整数，输出最少需要操作的次数。如果答案不存在，输出-1。
- 样例输入
++-+--+
-++--++
- 样例输出
4
解题思路：贪心，找到当前不同的和离当前最近的不同点，交换即可
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;
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 }
nyoj-915—— +-字符串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。