下午HDU的比賽，做得不好。一是有一個題目題意沒讀清楚，還有就是犯了兩個錯誤，在1006卡死了。
題目地址：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1006&cid=103
題意比較簡單，然后我想到一個對每個frosh的課程排序，然后對所有的排序，再計算。
開始寫了個得到TLE，我覺得不太可能有更好的算法，然后重寫，還是TLE，無奈我把數字轉換成字符串，一直WA。
結果我就卡在這個題目上兩個多小時，直到最后也沒做出來。
剛剛終于找到了錯誤：
第一個程序TLE是因為數組范圍開小了，結果沒有RE，只是TLE，詭異呀～～
第二個程序是排序用的qsort，然后比較函數開始照著字符串數組排序打的，然而字符串在結構體里面，居然可以比較而且跟我想的一樣，在我的機器上沒問題，交上去就WA了。
下面是兩個方法AC后的程序（用注釋標記了錯誤的地方）：
1 # include <iostream>
2 using namespace std;
3
4 //開始一直TLE，都是因為N的范圍小了——開始定為5555
5 # define N 10010
6
7 typedef struct node {
8 int no[5];
9 };
10
11 node man[ N ];
12 int n;
13
14 int cmp1( const void *a, const void *b)
15 {
16 return (*(int *)a - *(int *)b);
17 }
18
19 void init()
20 {
21 for ( int i = 0; i < n; i ++ )
22 {
23 for ( int j = 0; j < 5; j ++ )
24 {
25 scanf( "%d", &man[i].no[j] );
26
27 }
28 qsort(man[i].no, 5, sizeof(man[i].no[0]), cmp1);
29 // cout << man[i].no[0] << endl; ///
30 }
31 }
32
33 int cmp2( const void *a, const void *b )
34 {
35 node *aa = (node *)a;
36 node *bb = (node *)b;
37 if ( aa->no[0] != bb->no[0] )
38 {
39 return aa->no[0] > bb->no[0] ? 1: -1;
40 }
41 if ( aa->no[1] != bb->no[1] )
42 {
43 return aa->no[1] > bb->no[1] ? 1: -1;
44 }
45 if ( aa->no[2] != bb->no[2] )
46 {
47 return aa->no[2] > bb->no[2] ? 1: -1;
48 }
49 if ( aa->no[3] != bb->no[3] )
50 {
51 return aa->no[3] > bb->no[3] ? 1: -1;
52 }
53 return aa->no[4] - bb->no[4];
54 }
55
56 inline bool is_same( int a, int b )
57 {
58 for ( int i = 0; i < 5; i ++ )
59 {
60 if (man[a].no[i] != man[b].no[i]) return false;
61 }
62 return true;
63 }
64
65 void solve()
66 {
67 qsort(man, n, sizeof(man[0]), cmp2);
68 int ans = 1, max = 1;
69 int tmp = 1, t = 1;
70 bool flag;
71 for (int i = 1; i < n; i ++ )
72 {
73 if ( is_same(i, i-1) ) tmp++;
74 else
75 {
76 // cout << tmp << endl; ///
77 if (tmp > max)
78 {
79 max = tmp;
80 t = tmp;
81 ans = max; //
82 }
83 else if (tmp == max)
84 {
85 t += tmp;
86 if ( t > ans ) ans = t;
87 }
88 tmp = 1;
89 }
90 }
91 if ( n > 1 && is_same(n-1, n-2) )
92 {
93 if (tmp > max)
94 {
95 max = tmp;
96 ans = max; //
97 }
98 else if (tmp == max)
99 {
100 t += tmp;
101 if ( t > ans ) ans = t;
102 }
103 }
104 printf("%d\n", ans);
105 }
106
107 int main()
108 {
109 while ( true )
110 {
111 scanf("%d", &n);
112 if ( n == 0 ) break;
113 init();
114 solve();
115 }
116 return 0;
117 }
118
代碼二：
1 # include <iostream>
2 using namespace std;
3
4 # define N 10010
5
6 typedef struct node {
7 int no[5];
8 char s[16];
9 };
10
11 node man[ N ];
12 int n;
13
14 int cmp1( const void *a, const void *b)
15 {
16 return (*(int *)a - *(int *)b);
17 }
18
19 void to_string(int a)
20 {
21 man[a].s[0] = man[a].no[0]/100 + '0';
22 man[a].s[1] = man[a].no[0]%100/10 + '0';
23 man[a].s[2] = man[a].no[0]%10 + '0';
24
25 man[a].s[3] = man[a].no[1]/100 + '0';
26 man[a].s[4] = man[a].no[1]%100/10 + '0';
27 man[a].s[5] = man[a].no[1]%10 + '0';
28
29 man[a].s[6] = man[a].no[2]/100 + '0';
30 man[a].s[7] = man[a].no[2]%100/10 + '0';
31 man[a].s[8] = man[a].no[2]%10 + '0';
32
33 man[a].s[9] = man[a].no[3]/100 + '0';
34 man[a].s[10] = man[a].no[3]%100/10 + '0';
35 man[a].s[11] = man[a].no[3]%10 + '0';
36
37 man[a].s[12] = man[a].no[4]/100 + '0';
38 man[a].s[13] = man[a].no[4]%100/10 + '0';
39 man[a].s[14] = man[a].no[4]%10 + '0';
40
41 man[a].s[15] = '\0';
42 }
43
44 void init()
45 {
46 for ( int i = 0; i < n; i ++ )
47 {
48 scanf( "%d%d%d%d%d", &man[i].no[0], &man[i].no[1],&man[i].no[2], &man[i].no[3], &man[i].no[4]);
49 qsort(man[i].no, 5, sizeof(man[i].no[0]), cmp1);
50 to_string(i);
51 // cout << man[i].s << endl; ////
52 }
53 }
54 /*
55 int cmp2(const void *a,const void *b)
56 {
57 return(strcmp((char*)a,(char*)b));
58 }
59 */
60 int cmp2(const void *a,const void *b) //一直WA都是因為這個函數寫錯了,見上
61 {
62 node *aa = (node *)a;
63 node *bb = (node *)b;
64 return(strcmp(aa->s,bb->s));
65 }
66
67 void solve()
68 {
69 qsort(man, n, sizeof(man[0]), cmp2); ///
70
71 int ans = 1, max = 1;
72 int tmp = 1, t = 1;
73 bool flag;
74 for (int i = 1; i < n; i ++ )
75 {
76 if ( strcmp( man[i].s, man[i-1].s ) == 0 ) tmp++;
77 else
78 {
79 if (tmp > max)
80 {
81 max = tmp;
82 t = tmp;
83 ans = max; //
84 }
85 else if (tmp == max)
86 {
87 t += tmp;
88 if ( t > ans ) ans = t;
89 }
90 tmp = 1;
91 }
92 }
93 if ( n > 1 && strcmp( man[n-1].s, man[n-2].s ) == 0 )
94 {
95 if (tmp > max)
96 {
97 max = tmp;
98 ans = max; //
99 }
100 else if (tmp == max)
101 {
102 t += tmp;
103 if ( t > ans ) ans = t;
104 }
105 }
106
107 printf("%d\n", ans);
108 }
109
110 int main()
111 {
112 while ( true )
113 {
114 scanf("%d", &n);
115 if ( n == 0 ) break;
116 init();
117 solve();
118 }
119 return 0;
120 }
121
posted on 2008-01-24 19:14
R2 閱讀(1078)
評論(0) 編輯 收藏 引用 所屬分類:
Memo