山東理工大學ACM 1294：選票統計 - C語言解題詳解

題目描述

某校學生會主席選舉，有 m 位候選人（編號 1~m，0 < m < 1000），n 名學生投票（0 < n < 30000）。每人投一票，選一名候選人。統計得票最高的候選人編號及其得票數。

輸入格式

第一行：m n
第二行起：n 個整數，表示每位學生投票的候選人編號。

輸出格式

第一行：得票最多的候選人編號
第二行：該候選人得票數

範例

輸入範例

3 10
1 2 3 2 3 1 2 3 1 3

輸出範例

3
4

解題思路

經典的計數問題。開一個大小為 m+1 的陣列 cnt[]，索引即候選人編號，遍歷所有選票累加計數，最後掃描陣列找最大值及其索引。

參考代碼 (C語言)

#include <stdio.h>

int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    int cnt[1001] = {0};
    for (int i = 0; i < n; i++) {
        int k; scanf("%d", &k);
        if (k >= 1 && k <= m) cnt[k]++;
    }
    int max_votes = 0, winner = 0;
    for (int i = 1; i <= m; i++) {
        if (cnt[i] > max_votes) {
            max_votes = cnt[i];
            winner = i;
        }
    }
    printf("%d\n%d\n", winner, max_votes);
    return 0;
}

複雜度分析

• 時間複雜度：O(n + m)，n ≤ 30000，m ≤ 1000，極快。
• 空間複雜度：O(m) 計數陣列。

注意事項

• 候選人編號從 1 開始，陣列大小開 m+1 方便直接用編號做索引。
• 題目未說明平票情況，代碼採用「先遇到的最大值勝出」（即編號較小者優先），通常符合預期。
• 輸入可能分多行，用 scanf 循環讀取 n 次即可自動跨行。