|
日历
统计
- 随笔 - 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 中关于快速排序的算法，按照它上面写出来的。 回复 更多评论
|