內容
Waterloo 大學的新鮮人由於興趣不同，對於課程的選擇不盡相同，而校方希望他們所選的課程儘量一致，所以設立了一個獎項，頒發給 選擇的「課程組合」為「最受歡迎的課程組合」的學生。
輸入
輸入有多組測試資料，每組資料的開頭有一個整數 n 表示新生的人數( 1 <= n <= 10000 )，接下來有 n 列分別為這些新生所選擇的課程代號，每列有 5 個表示課程代號的整數，其值介於 100 ~ 499。當 n = 0 表示測試資料結束。
3
100 101 102 103 488
100 200 300 101 102
103 102 101 488 100
3
200 202 204 206 208
123 234 345 456 321
100 200 300 400 444
0
輸出
一組課程的受歡迎程度視所有剛好選擇該組課程的學生人數而定，如果沒有其他「課程組合」的人數比此「課程組合」的人數高，則該課程為最 受歡迎的「課程組合」，請對每組測試資料輸出選擇最受歡迎的「課程組合」的人數。
2
3
解題思路
解題方向 :
由於”選課順序”不影響”課程組合”，所以先將輸入的選課排序好避免因不同的”選課順序”被視為不同的”課程組合”。
將排序好的課程組合打成一個雜湊值(Hash)。
查看雜湊表的 Hash，如果已經有 Hash 存過得到的雜湊值，則該 Hash 的 Count+1，反之則新增一個 Key 為得到的雜湊值的 Hash，並將該 Hash 新增至雜湊表。 (這段的 Hash 指的是 struct Hash)
輸入完全部課程組合後，再完整的遍歷一次雜湊表即可取得 “最受歡迎的課程組合”的總修課人數。
一些注意事項 :
- 雜湊表大小設為 2 的次方數，這樣可以在存雜湊值進去時用 & 取代 % 來加速。
- 因為有多組輸入，所以每次計算完都要清空一次雜湊表。
- “最受歡迎的課程組合”可以是複數堂，也就是說，當”最受歡迎的課程組合”人數為 3，且有 3 堂修課人數為 3 的課程組合時，答案應該是 3(堂) * 3(人) = 9 人。
- 雜湊運算並不是安全的判斷方式，因為可能會產生雜湊碰撞(兩不同的資料得到一樣的雜湊資)，但由於發生機率過低，所以這裡無視這個問題。
完整程式碼
AC (62ms, 344KB)
#include <stdio.h>
#include <stdlib.h>
typedef struct Hash
{
unsigned int Key;
int Count;
struct Hash* Next;
}Hash;
Hash HashTable[1024];
unsigned int list[5];
int n;
int cmp(const unsigned int* lhs, const unsigned int* rhs)
{
return *lhs - *rhs;
}
inline unsigned int toHash(unsigned int src[])
{
return (src[0] << 28) + (src[1] << 21) + (src[2] << 14) + (src[3] << 7) + src[4];
}
inline void AddHash(unsigned int hash)
{
Hash* now = &HashTable[hash & 1023];
while (now->Key != hash)
{
if (now->Next == NULL)
{
now = now->Next = malloc(sizeof(Hash));
now->Key = hash;
now->Next = NULL;
now->Count = 1;
return;
}
now = now->Next;
}
now->Count++;
}
int PopularityCount()
{
int max = 0, count = 0;
Hash* now, * tmp;
for (int i = 0; i < 1024; i++)
{
if (HashTable[i].Next != NULL)
{
now = HashTable[i].Next;
do
{
if (max <= now->Count)
{
if (max == now->Count)
count += max;
else
count = max = now->Count;
}
tmp = now;
now = now->Next;
free(tmp);
} while (now != NULL);
HashTable[i].Next = NULL;
}
}
return count;
}
int main()
{
while (scanf(" %d", &n) == 1 && n)
{
for (int i = 0; i < n; i++)
{
scanf(" %u %u %u %u %u", &list[0], &list[1], &list[2], &list[3], &list[4]);
qsort(list, 5, sizeof(unsigned int), cmp);
AddHash(toHash(list));
}
printf("%d\n", PopularityCount());
}
return 0;
}
|
