Sicily 1299 Academy Awards：統計提名頻率預測最佳影片

問題描述

給定多個獎項的提名名單，每個獎項有若干提名影片。規則：
1. 所有出現的影片都有機會
2. 提名次數最多的影片獲獎
3. 平票時選名單中最早出現的

解法：Map + Vector

• map：統計每部影片提名次數
• vector：按出現順序記錄所有提名（含重複）

算法流程

1. 讀入獎項數n
2. 對每個獎項：讀入獎項名、提名數m、m個影片名
3. 每個影片：push_back到vector，map中計數+1
4. 遍歷vector，找map值最大且最早出現的影片

關鍵代碼

map mp;
vector v;
string award, film, winner;
int n, m, maxCnt = 0;

while(cin >> n && n) {
    mp.clear(); v.clear();
    
    while(n--) {
        cin >> award >> m;
        for(int i=0; i> film;
            v.push_back(film);
            mp[film]++; // 自動處理首次插入
        }
    }
    
    maxCnt = 0;
    for(int i=0; i maxCnt) {
            maxCnt = mp[v[i]];
            winner = v[i]; // 首次達到最大值即最早出現
        }
    }
    cout << winner << endl;
}

關鍵點

• vector保持輸入順序，自然解決平票優先級
• map自動處理鍵不存在時的初始化（值為0）
• 輸入以n=0結束，多測試用例
• 影片名無空格，直接cin讀取

複雜度

時間：O(總提名數 × log(不同影片數))，map操作log級
空間：O(不同影片數 + 總提名數)
數據範圍小（n≤100, m≤10），極輕鬆通過。