NYOJ915 +-字符串

原題鏈接

主要思路：從左到右，逐個比較，若有不同，標記此不同地點，並向右搜尋首個相同點，從該點開始挨個與左邊位置交換並統計交換次數。

#include 
#include 
#define MAX 5000 + 2
char str[MAX], str2[MAX];

int find(int i){
	int j = i, count = 0;
	char t;
	while(str[j] != str2[i])
		++j;
	while(j > i){
		t = str[j];
		str[j] = str[j - 1];
		str[j - 1] = t;
		--j;
		++count;
	}
	return count;
}

int main(){
	int count;
	while(scanf("%s%s", str, str2) == 2){
		int a = 0, b = 0;
		for(int i = 0; str[i] != '\0'; ++i)
			if(str[i] == '-') ++a;
		for(int i = 0; str2[i] != '\0'; ++i)
			if(str2[i] == '-') ++b;
		if(a != b){
			printf("-1\n");
			continue;
		}
		count = 0;
		for(int i = 0; str2[i] != '\0'; ++i){
			if(str[i] != str2[i])
				count += find(i);
		}
		printf("%d\n", count);
	}
	return 0;
}

優化後的代碼：思路有所改變。不再模擬整個過程，時間大幅縮短。

#include 
#include 
#define MAX 5000 + 2
char str[MAX], str2[MAX];

int main(){
	int count, ok, i, j;
	while(scanf("%s%s", str, str2) == 2){
		count = 0;
		for(i = 0, ok = 1; str2[i] != '\0'; ++i){			
			if(str[i] != str2[i]){
				for(j = i + 1, ok = 0; str[j] != '\0'; ++j)
					if(str[j] == str2[i]){
						count += j - i;
						str[j] = str[i];
						ok = 1;
						break;
					}				
			}
			if(!ok){
				printf("-1\n");
				break;
			}
		}
		if(ok) printf("%d\n", count);
	}
	return 0;
}