南阳题目915-+-字符串

向右看齐 2022-07-28 10:57 215阅读 0赞

## \+-字符串 ##

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 1

描述

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

输入

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

输出

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

样例输入

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

样例输出

4

来源

[NBOJ][]

上传者

这个题要弄清楚一点，就是要想次数最少，我们要逐次比较，找第一个不相等的，然后从第二个串里面找出最近的相等的与第二个串不想等的位置进行替换，算出移动的

次数，依次算下去，如果有一次不能找到，证明无解

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int main()
    {
    	char s1[5001],s2[5001];
    	int m,n,i,j,len,flag,Q;
    	while(scanf("%s%s",s1,s2)!=EOF)
    	{
    		len=strlen(s1);
    		Q=0;
    		int sum=0;
    		for(i=0;i<len;i++)
    		{
    			if(s1[i]!=s2[i]) 
    			{
    				flag=1;
    				for(j=i+1;j<len;j++)
    				{
    					if(s2[j]==s1[i])
    					{
    						sum+=j-i;
    						s2[j]=s2[i];	
    						flag=0;
    						break;
    					
    					}
    				}
    				if(flag)
    				{
    					Q=1;
    					break;
    				}
    			}
    		}
    		if(Q)
    		printf("-1\n");
    		else
    		printf("%d\n",sum);
    	 } 
    return 0;	
    }

[NBOJ]: http://acm.nyist.net/JudgeOnline/search_result.php?source=NBOJ

发表评论取消回复

表情：

评论列表（有 0 条评论，215人围观）

还没有评论，来说两句吧...

相关阅读

相关南阳题目915-+-字符串

\+-字符串时间限制： 1000 ms | 内存限制： 65535 KB 难度： 1 描述 Shiva得到了两个只有加号和减号的字符串，字串长度相同。Shiva一

向右看齐/ 2022年07月28日 10:57/ 0 赞/ 216 阅读

相关南阳题目198-数数

数数时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述我们平时数数都是喜欢从左向右数的，但是我们的小白同学最近听说德国人数数和我们有

ゞ浴缸里的玫瑰/ 2022年07月28日 00:28/ 0 赞/ 196 阅读

相关南阳题目169-素数

素数时间限制： 3000 ms | 内存限制： 65535 KB 难度： 1 描述走进世博园某信息通信馆，参观者将获得前所未有的尖端互动体验，一场充满创想和喜悦

川长思鸟来/ 2022年07月28日 00:28/ 0 赞/ 199 阅读

相关南阳题目168-房间安排

房间安排时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述 2010年上海世界博览会(Expo2010),是第41届世界博览会。于20

亦凉/ 2022年07月28日 00:28/ 0 赞/ 184 阅读

相关南阳题目113-字符串替换

字符串替换时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述编写一个程序实现将字符串中的所有"you"替换成"we" 输入输入

拼搏现实的明天。/ 2022年07月27日 14:46/ 0 赞/ 155 阅读

相关南阳题目111-分数加减法

分数加减法时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述编写一个C程序，实现两个分数的加减法输入输入包含多行数据每

刺骨的言语ヽ痛彻心扉/ 2022年07月27日 14:46/ 0 赞/ 181 阅读

相关南阳题目94-cigarettes

cigarettes 时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述 Tom has many cigarettes. We hyp

淡淡的烟草味﹌/ 2022年07月27日 13:56/ 0 赞/ 211 阅读

相关南阳题目57-6174问题

6174问题时间限制： 1000 ms | 内存限制： 65535 KB 难度： 2 描述假设你有一个各位数字互不相同的四位数，把所有的数字从大到小排序后得到a

ゝ一纸荒年。/ 2022年07月27日 13:48/ 0 赞/ 195 阅读

相关南阳题目218-Dinner

Dinner 时间限制： 100 ms | 内存限制： 65535 KB 难度： 1 描述 Little A is one member of ACM team.

逃离我推掉我的手/ 2022年07月26日 12:23/ 0 赞/ 222 阅读

相关南阳题目287-Radar

Radar 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述 Assume the coasting is an infinite s

末蓝、/ 2022年07月26日 04:11/ 0 赞/ 215 阅读