AT_abc008_2 [ABC008B] 投票 题解

题目理解

有 N 个人投票，每人投给一个名字（字符串）。
统计得票最多的名字并输出。
如果多个名字得票相同，输出任意一个即可。

---

解法一：使用 map 统计（最推荐）

核心思路

使用 map<string, int> 统计每个名字出现的次数，然后遍历找出最大值。

代码实现

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    map<string, int> votes;
    
    // 统计票数
    for (int i = 0; i < N; i++) {
        string name;
        cin >> name;
        votes[name]++;
    }
    
    // 找出得票最多的名字
    string winner;
    int maxVotes = 0;
    
    for (auto& p : votes) {
        if (p.second > maxVotes) {
            maxVotes = p.second;
            winner = p.first;
        }
    }
    
    cout << winner << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：O(N log M)，M 为不同名字的数量（最多 N）
• 空间复杂度：O(M)

---

解法二：使用 unordered_map（更快）

当不需要按字典序遍历时，unordered_map 的插入和查找是 O(1) 的。

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    unordered_map<string, int> votes;
    
    for (int i = 0; i < N; i++) {
        string name;
        cin >> name;
        votes[name]++;
    }
    
    string winner;
    int maxVotes = 0;
    
    for (auto& p : votes) {
        if (p.second > maxVotes) {
            maxVotes = p.second;
            winner = p.first;
        }
    }
    
    cout << winner << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：O(N) 平均
• 空间复杂度：O(M)

---

解法三：暴力枚举（适合理解）

N ≤ 100，可以直接用数组存储所有名字，然后双层循环统计。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    vector<string> names(N);
    for (int i = 0; i < N; i++) {
        cin >> names[i];
    }
    
    string winner;
    int maxVotes = 0;
    
    // 对每个名字统计出现次数
    for (int i = 0; i < N; i++) {
        int cnt = 0;
        for (int j = 0; j < N; j++) {
            if (names[i] == names[j]) {
                cnt++;
            }
        }
        if (cnt > maxVotes) {
            maxVotes = cnt;
            winner = names[i];
        }
    }
    
    cout << winner << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：O(N²) = 10000，完全可行
• 空间复杂度：O(N)

---

解法四：排序后统计

先对名字排序，然后遍历统计连续相同名字的数量。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    vector<string> names(N);
    for (int i = 0; i < N; i++) {
        cin >> names[i];
    }
    
    sort(names.begin(), names.end());
    
    string winner = names[0];
    int maxVotes = 1;
    int currentVotes = 1;
    
    for (int i = 1; i < N; i++) {
        if (names[i] == names[i - 1]) {
            currentVotes++;
        } else {
            currentVotes = 1;
        }
        
        if (currentVotes > maxVotes) {
            maxVotes = currentVotes;
            winner = names[i];
        }
    }
    
    cout << winner << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：O(N log N)（主要是排序）
• 空间复杂度：O(N)

---

样例验证

样例1

输入：
5
takoyaki
takoyaki
taiyaki
takoyaki
okonomiyaki

输出：takoyaki

统计结果：

• takoyaki: 3 次 ✓
• taiyaki: 1 次
• okonomiyaki: 1 次

样例2

输入：
3
a
b
c

输出：a

所有名字都是 1 次，输出任意一个（这里输出 a）

---

总结

解法	时间复杂度	空间复杂度	推荐场景
map	O(N log M)	O(M)	通用，代码简洁
unordered_map	O(N) 平均		追求效率
暴力枚举	O(N²)	O(N)	N 很小时教学用
排序	O(N log N)		需要顺序输出时

关键点

1. 无需处理平局：题目允许输出任意一个得票最多的名字
2. 字符串可以重复：使用 map 或 unordered_map 自动处理
3. 数据范围小：即使 O(N²) 也能通过

最推荐代码（简洁高效）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    map<string, int> mp;
    string s;
    while (cin >> s) mp[s]++;
    string ans;
    int mx = 0;
    for (auto [name, cnt] : mp) {
        if (cnt > mx) {
            mx = cnt;
            ans = name;
        }
    }
    cout << ans << endl;
}