问题分析

这是一个简单的统计问题，需要找出得票最多的题目。关键点在于：

1. 统计频率：计算每个题目编号获得的票数
2. 找出众数：找到出现次数最多的值
3. 处理特殊情况：如果所有题目得票数相同，输出 -1
4. 输出格式：按要求输出最多票数的题目数量和编号

算法思路

核心思想：哈希统计 + 遍历检查

使用 map 来统计每个题目编号的出现次数，然后找出最大值并收集结果。

算法步骤

1. 初始化：清空 map，准备统计新一组数据
2. 统计票数：遍历所有投票，用 map 记录每个题目的得票数
3. 找出最大值：在统计过程中记录最大票数
4. 检查特殊情况：如果所有题目的票数都等于最大值，输出 -1
5. 输出结果：否则输出最多票数的题目数量和编号（按升序排列）

代码详解

1. 数据结构和初始化

map<int, int> mp;  // 题目编号 -> 票数 的映射

使用 map 的优势：

• 自动按键（题目编号）排序
• 支持大范围编号（最大 $10^9$）
• 方便统计和遍历

2. 统计票数并找出最大值

int ans = 0;  // 记录最大票数
for (int i = 1; i <= n; ++i) {
    int num;
    cin >> num;
    mp[num]++;            // 票数+1
    if (mp[num] > ans) {  // 更新最大值
        ans = mp[num];
    }
}

优化：在输入过程中同时更新最大值，避免后续再次遍历寻找最大值。

3. 统计最多票数的题目数量

int cnt = 0;
for (auto it = mp.begin(); it != mp.end(); ++it) {
    if (ans == (it->second)) {
        cnt++;
    }
}

4. 特殊情况处理和结果输出

// 检查是否所有题目票数相同
if (mp.size() == cnt) {
    cout << -1 << endl;
} else {
    cout << cnt << endl;
    bool flag = 1;
    
    // 输出最多票数的题目编号（已按升序排列）
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        if (ans == (it->second)) {
            if (flag) {
                cout << it->first;
                flag = 0;
            } else {
                cout << " " << it->first;
            }
        }
    }
    cout << endl;
}

复杂度分析

时间复杂度

• 统计票数：$O(n \log n)$（map 的插入操作）
• 遍历统计：$O(n)$
• 总复杂度：$O(n \log n)$，在 $n \leq 100000$ 时完全可行

空间复杂度

• $O(n)$：存储 map 需要线性空间

算法正确性

边界情况处理

1. 所有票数相同：正确输出 -1
2. 单个题目得票最多：正确输出该题目编号
3. 多个题目并列第一：正确输出所有并列的题目编号
4. 大编号处理：使用 map 支持 $10^9$ 范围的编号

算法优势

1. 简洁高效：代码逻辑清晰，时间复杂度合理
2. 通用性强：适用于各种数据分布
3. 格式正确：严格符合题目输出要求
4. 易于理解：算法逻辑直观，易于维护

总结

本题通过使用 map 进行频率统计，结合简单的遍历检查，高效解决了投票统计问题。算法充分利用了 STL 容器的特性：

• map 的自动排序功能
• map 对大范围键值的支持
• 简洁的遍历和统计语法

该解法在代码复杂度和运行效率之间取得了良好平衡，能够正确处理所有测试数据。