UVa11286-Conformity 解題心得

     

Waterloo大學的新鮮人由於興趣不同，對於課程的選擇不盡相同，而校方希望他們所選的課程盡量一致，所以設立了一個獎項，頒發給 選擇的「課程組合」為「最受歡迎的課程組合」的學生。

      輸入有多組測試資料，每組資料的開頭有一個整數 n 表示新生的人數(1 <= n <= 10000)，接下來有 n 列分別為這些新生所選擇的課程代號，每列有五個表示課程代號的整數，其值介於100~499。當 n = 0 表示測試資料結束。

      一組課程的受歡迎程度視所有剛好選擇該組課程的學生人數而定，如果沒有其他「課程組合」的人數比此「課程組合」的人數高，則該課程為最受歡迎的「課程組合」，請對每組測試資料輸出最受歡迎的「課程組合」的人數。

Sample Input

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

Output for Sample Input

2

3

==================================分割線========================================

這題有幾個需要注意的地方

1.重點是選課的組合!!選課的先後順序並不重要。先選100在選101跟先選101在選100是一樣的組合。

2.暴力法去掃每一個課程會超過限制的時間，所以這題的重點就在於運用map，PYTHON的話則是運用dict，這題則我用PYTHON解，所以用的是dict。

3.先將課程排序後如103 102 101 488 100變成100 101 102 103 488，再把100 101 102 103 488當成dict的KEY。

4.未來只要出現同樣一的一組課程，則dict[選課組合] += 1;

程式碼如下

def check():
    while 1:
        n = int(input())
        if n == 0:
            break;
        b = {}
        a = [[0 for i in range(5)] for j in range(n)]
        ss = []
        ss_a = ss.append
        max = 0;
        for i in range(n):
            a[i] = input().split()
            a[i].sort()
            if(b.get(str(a[i])) == None):
                ss_a((str(a[i])))
                b[str(a[i])] = 1
            else:
                b[str(a[i])] += 1
            if max < b[str(a[i])]:
                max = b[str(a[i])]

        sum = 0;
        for i in ss:
            if b[i] == max:
                sum += max;
        print(sum)


check()