|
日歷
統計
- 隨筆 - 30
- 文章 - 0
- 評論 - 51
- 引用 - 0
導航
常用鏈接
留言簿(4)
隨筆分類
隨筆檔案
ACM
搜索
最新評論
閱讀排行榜
評論排行榜
|
在上周開始做北大acm1002題，經過幾天的分析和參考別人的代碼，最后終于提交成功了。在這里把代碼貼出來，和大家分享，也懇請大家指出寫不好的地方。在網上搜到了另外一個人對這道題的解法，他是解法，推薦大家看看。
1 #include <stdlib.h>
2#include <stdio.h>
3typedef int TelNumber;
4  int toNumber[26] =  {2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,-1,7,7,8,8,8,9,9,9,-1};
5
6void SortNumber(TelNumber *tel, int left, int right)
7{
8 int j,i;
9 TelNumber temp;
10 do
11  {
12 i = left;
13 j = right;
14 temp = tel[(i+j)/2];
15 do
16 {
17 while(tel[i] < temp) i++;
18 while(tel[j] > temp) j--;
19 if(i > j)
20 break;
21 if(i < j)
22 {
23 TelNumber t = tel[i];
24 tel[i] = tel[j];
25 tel[j] = t;
26 }
27 i++;j--;
28 }while(i <= j);
29
30 if(j-left <= right -i)
31 {
32 if(left < j)
33 SortNumber(tel,left, j);
34 left = i;
35 }
36 else
37 {
38 if(i < right)
39 SortNumber(tel, i, right);
40 right = j;
41 }
42 }while(left < right);
43 }
44
45int main(int argc, char* argv[])
46{
47 int count;
48 int i;
49 int t = 1;
50 int bSame = 0;
51 TelNumber tel[100000];
52 scanf("%d\n", &count);
53 for( i = 0; i < count;i++)
54 {
55 char ch;
56 tel[i] = 0;
57 while( ch = getchar(), ch != '\n')
58 {
59 if(ch == '-')
60 continue;
61 else if (ch >= '0' && ch <= '9')
62 tel[i] = tel[i]*10 + (ch-'0');
63 else if((ch >= 'A' && ch <= 'P') || (ch >= 'R' && ch <= 'Y'))
64 tel[i] = tel[i]*10 + toNumber[ch-'A'];
65 }
66 }
67
68 SortNumber(tel, 0, count-1);
69 for(i = 0; i < count;)
70 {
71 for(t = i+1; (t < count) && (tel[i] == tel[t]); t++)
72 ;
73 if(t-i > 1)
74 {
75 bSame = 1;
76 printf("%03d-%04d %d\n", tel[i]/10000, tel[i]%10000, t-i);
77 }
78 i=t;
79 }
80 if(bSame==0)
81 printf("No duplicates.\n");
82 return 1;
83}
評論:
-
# re: acm1002探討
Posted @ 2008-05-19 16:39
最好把題也一起貼出來，只是給個鏈接，省得再去找了。 回復 更多評論
-
# re: acm1002探討
Posted @ 2008-05-19 17:36
為什么不用qsort或者STL的sort... 回復 更多評論
-
# re: acm1002探討
Posted @ 2008-05-20 08:08
謝謝劉峰的提醒。
回復 更多評論
-
# re: acm1002探討
Posted @ 2008-05-20 08:10
我是想自己寫一個快速排序，但是自己寫的老是超時，所以參考了.Net 中關于快速排序的算法，按照它上面寫出來的。 回復 更多評論
|