Welcome to Leon's Blog

日歷

2009年3月

日

一

二

三

四

五

六

統(tǒng)計(jì)

隨筆 - 30
文章 - 0
評(píng)論 - 51
引用 - 0

導(dǎo)航

常用鏈接

留言簿(4)

隨筆分類

隨筆檔案

ACM

搜索

閱讀排行榜

評(píng)論排行榜

acm1002探討

在上周開始做北大acm1002題，經(jīng)過(guò)幾天的分析和參考別人的代碼，最后終于提交成功了。在這里把代碼貼出來(lái)，和大家分享，也懇請(qǐng)大家指出寫不好的地方。在網(wǎng)上搜到了另外一個(gè)人對(duì)這道題的解法，他是解法，推薦大家看看。

#include <stdlib.h>
2

#include <stdio.h>
3

typedef 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

void 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

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

int 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

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

}

posted on 2008-05-19 10:44 Leon916 閱讀(1503) 評(píng)論(4) 編輯收藏引用

評(píng)論:

# re: acm1002探討劉峰 Posted @ 2008-05-19 16:39
最好把題也一起貼出來(lái)，只是給個(gè)鏈接，省得再去找了。回復(fù) 更多評(píng)論
# re: acm1002探討 winsty Posted @ 2008-05-19 17:36
為什么不用qsort或者STL的sort... 回復(fù) 更多評(píng)論
# re: acm1002探討 Leon916 Posted @ 2008-05-20 08:08
謝謝劉峰的提醒。
回復(fù) 更多評(píng)論
# re: acm1002探討 Leon916 Posted @ 2008-05-20 08:10
我是想自己寫一個(gè)快速排序，但是自己寫的老是超時(shí)，所以參考了.Net 中關(guān)于快速排序的算法，按照它上面寫出來(lái)的。回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理


Copyright © Leon916	Powered by: 博客園模板提供：滬江博客