uva:10602 - Editor Nottoobad（貪心）

uva:10602 - Editor Nottoobad（貪心）

題目：10602 - Editor Nottoobad

題目大意：有一個機子它由press的動作還有copy和delete字符的動作。給一組字符串，問要輸入這樣的一組字符串，最少要執行的press動作。

解題思路：將這一組字符串按照ascall碼排序後，這樣前後兩個字符串的相似度是比較高的。然後後一個字符串和前一個字符串相比，看有多少相同的可以copy，就只要統計一下不相同的字符個數。這題比較迷惑人的是題目一直說要求第一個字符串一定要先執行press動作，但是輸出卻可以任意給一種，不一定是要第一個字符串在第一個位置的那種情況。

代碼：

#include 
#include 
#include 
using namespace std;

const int N = 105;
//char first[N];
struct WORDS{

	char str[N];
}words[N];

int cmp (const WORDS & w1, const WORDS & w2) {

	return strcmp(w1.str, w2.str) < 0 ? true :false;
}

int caculate (int n) {
	
	int sum = 0;
	int len;
	int k;
	for (int i = 1; i < n; i++) {

		len = strlen(words[i].str);
		k = 0;
		while (words[i - 1].str[k]  && words[i - 1].str[k] == words[i].str[k]) {

			k++;
		}
		sum += len - k;
	}
	return sum + strlen (words[0].str);
}


int main () {

	int t;
	scanf ("%d", &t);
	while (t--) {

		int n;
		scanf ("%d", &n);
		for (int i = 0; i < n; i++)
			scanf ("%s", words[i].str);
		//memcpy (first, words[0].str, sizeof (first));
		sort (words, words + n, cmp);
		printf ("%d\n", caculate(n));	
		for (int i = 0; i < n; i++)
			printf("%s\n", words[i].str);
	}
	return 0;
}