这题想了好久啊!!!还各种小细节出错,我太菜了,要更加努力才行
这回要把解题思路写一写,不然估计过几天就忘了
解题思路:
长条固定,移动短条去匹配长条,有三种情况
第一种,在短条在长条范围内移动匹配
第二种,短条在长条的左边移动匹配
第三种,短条在长条右边,与左边的情况同理,右移到0与5相等的位置停止匹配
实现代码
#include<stdio.h> #include<string.h> #include <stdlib.h> #define maxn 100 int match(int b1[maxn],int b2[maxn],int len1,int len2) { // int len1=length1,len2=length2; int min=len1+len2,flag=0; for(int k=0;k<=len2-len1;k++)//短串在长串内的情况 { int t=0; for(;t<len1;t++)//从左到右,短串移动匹配 { //printf("b1[%d]=%d b2[%d]=%d\n",t,b1[t],t+k,b2[t+k]); if(b1[t]+b2[t+k]>3) { break; } } if(t==len1){flag =1;break;} } if(flag==1) {min=len2;return (min);} else { int r=1; for(;r<len1;r++)//短串在左边,向左移动的情况 { int s=0; for(;s<len1-r;s++)//逐个匹配 { if(b1[s+r]+b2[s]>3){break;} } if(s==len1-r){flag=1;break;} } if(flag==1) {min=len2+r;} int n=1;flag=0; for(;n<len1;n++)//短串在右边的,向右移动情况 { int m=len1-1; for(;m>=n;m--)//逐个匹配 { //printf("b1[%d]=%d b2[%d]=%d\n",m-n,b1[m-n],m-len1+len2,b2[m]); if(b1[m-n]+b2[m-len1+len2]>3){break;} } if(m<n){flag=1;break;} } if(flag==1){min=len2+n>min?min:len2+n ;return min;} else{return min;} } } int main() { char a1[maxn],a2[maxn]; int c1[maxn]={0},c2[maxn]={0}; gets(a1); gets(a2); int length1=strlen(a1); int length2=strlen(a2); for(int i=0;i<length1;i++) { c1[i]=a1[i]-48;//'0'的ASCII码=48 } for(int j =0;j<length2;j++) { c2[j]=a2[j]-48; } int num=length1<=length2?match(c1,c2,length1,length2):match(c2,c1,length2,length1); printf("Min_length=%d",num); }
https://vjudge.net/problem/UVA-1588