学步园

题目不再说了，由于是刚开始做poj上面的题，很是吃力。这道题提交了好多次，有一次是TLE。我觉得主要是由于排序的关系。之前用的是插入排序，即将val[i]赋值给array[i]的时候，进行插入排序，复杂度为O(n^2+n^2+n)结果就超时了。后来自己实现了一个快速排序，变成O(n^2+nlogn+n)。

#include <cstdio><br /> #include <cstdlib><br /> #include <cstring><br /> #define MAX 100000<br /> using namespace std;<br /> char hash[] = {'2','2','2','3','3','3','4','4','4','5','5','5',<br /> '6','6','6','7','Q','7','7','8','8','8','9','9','9','Z'};<br /> char key[MAX][100] = {{0}};<br /> char val[MAX][100] = {{0}};<br /> char *array[MAX] = {NULL};</p> <p>void convert (char key[], int j) {<br /> int i = 0, k = 0, count = 0;<br /> while (key[i] != '/0') {<br /> if (count == 3) {<br /> val[j][k] = '-';<br /> ++count;<br /> ++k;<br /> continue;<br /> }<br /> else if (key[i] == '-')<br /> ++i;<br /> else if ('A' <= key[i] && key[i] <= 'Z') {<br /> val[j][k] = hash[key[i]-'A'];<br /> ++count;<br /> ++k;<br /> ++i;<br /> }<br /> else if ('0' <= key[i] && key[i] <= '9') {<br /> val[j][k] = key[i];<br /> ++count;<br /> ++k;<br /> ++i;<br /> }<br /> };<br /> }</p> <p>void swap (char*& p1, char*& p2) {<br /> char *temp = p1;<br /> p1 = p2;<br /> p2 = temp;<br /> }<br /> void sort (char* s[], int begin, int end) {<br /> if (begin >= end)<br /> return;<br /> int mid = (begin + end)/2;<br /> if (strcmp(s[begin], s[end]) > 0)<br /> swap(s[begin], s[end]);<br /> if (strcmp(s[mid], s[end]) > 0)<br /> swap(s[mid], s[end]);<br /> else if (strcmp(s[mid], s[begin]) < 0)<br /> swap(s[mid], s[begin]);</p> <p> int i = begin, j = end-1;<br /> while (i <= j) {<br /> if (strcmp(s[i], s[end]) < 0) {<br /> ++i;<br /> continue;<br /> }<br /> if (strcmp(s[j], s[end]) > 0) {<br /> --j;<br /> continue;<br /> }<br /> swap(s[i], s[j]);<br /> ++i;<br /> --j;<br /> };</p> <p> swap(s[i], s[end]);<br /> sort(s, begin, i-1);<br /> sort(s, i+1, end);<br /> }</p> <p>void poj1002 () {<br /> int d;<br /> scanf("%d", &d);<br /> int i = 0;<br /> while (i < d) {<br /> scanf("%s", key[i]);<br /> ++i;<br /> };<br /> for (int j=0; j<d; ++j) {<br /> convert(key[j], j);<br /> array[j] = val[j];<br /> }<br /> sort(array, 0, d-1);<br /> int count = 1, flag = 0;<br /> for (int j=0,k=1; j<d;) {<br /> if (k < d) {<br /> if (strcmp(array[j], array[k]) == 0) {<br /> ++count;<br /> ++k;<br /> continue;<br /> }<br /> else if (count > 1) {<br /> flag = 1;<br /> printf("%s %d/n", array[j], count);<br /> count = 1;<br /> }<br /> j = k;<br /> ++k;<br /> }<br /> else {<br /> if (count > 1) {<br /> flag = 1;<br /> printf("%s %d/n", array[j], count);<br /> }<br /> break;<br /> }<br /> }<br /> if (!flag)<br /> printf("No duplicates./n");<br /> }<br /> int main() {<br /> poj1002();<br /> return 0;<br /> }<br />