uva 10602 Editor Nottoobad(排序)

题目大意：要输入n个单词，现在有三种操作， 1、输入一个字符，需要按下一次按键。 2、通过声控删除一个字符。3、通过声控复制一遍上面的单词。现在要求按最少的按键来完成输入，并且输出输入的顺序。

解题思路：因为有复制这一功能，所以每次输入一个单词之后要找另一个与它相似度最近的一个。比较两个单词对应的不同字符个数，对于两个不同长度的单词，后面的单词长的话要计算多出的部分，因为是再输入的，要是短的话就不需要计算，因为是通过声控删除的。

#include <string.h>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

bool cmp(const string &a, const string &b)	{ return a < b;}

const int N = 105;

string tmp[N];

int main() {

    int cas, n, cnt, end;

    cin >> cas;

    while (cas--) {

	cin >> n;

	for (int i = 0; i < n; i++)

	    cin >> tmp[i];

	sort(tmp, tmp + n);

	cnt = tmp[0].size();

	for(int i = 1 ; i < n ; i++){

	    if(tmp[i][0] != tmp[i - 1][0]){

		cnt += tmp[i].size();

		continue;

	    }

	    int j;

	    for(j = 0; j < tmp[i - 1].size(); j++){

		if(tmp[i - 1][j] != tmp[i][j]) {

		    break;

		}

	    }

	    cnt += tmp[i].size() - j;

	}

	cout << cnt << endl;

	for (int i = 0; i < n; i++)

	    cout << tmp[i] << endl;

    }

    return 0;

}

巴特西

uva 10602 Editor Nottoobad(排序)

最新文章

热门文章