Uol 2025 Wk2 题解
Recount 问题描述 最近的学校董事会选举竞争异常激烈：提案内容包括互换中小学的上学时间，一项备受争议的禁止在校穿着运动服的新着装规定，以及一项旨在提高房地产税以资助新橄榄球训练设施的提案，诸如此类的议题层出不穷。现在，距离投票站关闭已过去数小时，但获胜者仍未揭晓！ 在绝望之中，选举官员们求助于您，请您编写一个程序来统计选票！ 输入 输入包含一个单一的测试用例，即一张已投选票的列表。输入中的每一行都包含一位被投票的候选人的名字。一个名字可能由多个单词组成，以空格分隔。单词包含字母或连字符，但不含其他标点符号。列表中至少有2张选票。选票列表以包含字符 *** 的单行结束。这一行不应被计入票数。最多可以有100,000张有效选票。 输出 如果某位候选人获得了简单多数或绝对多数的选票（即，票数超过任何其他候选人），则输出这位候选人的名字！如果没有候选人获得简单多数，则输出：“ Runoff!”（别忘了包含感叹号！） 代码 #include <iostream> #include <string> #include <unordered_map> #include <algorithm> // using namespace std; // 为简洁起见，在单个文件中可以如此使用 namespace recount { int main(istream &cin, ostream &cout) { // 使用 unordered_map 存储每位候选人的票数。 // 键是候选人的名字（字符串），值是他们的票数（无符号长整型）。 std::unordered_map<std::string, unsigned long> m = std::unordered_map<std::string, unsigned long>(); std::string line; // 逐行读取选票，直到遇到哨兵值 "***"。 while(std::getline(cin, line)) { if(line == "***") { break; } // 为当前行所指的候选人增加票数。 // 如果候选人尚不存在于哈希表中，则会以计票数为1被添加进去。 m[line]++; } // 初始化一个字符串来存放获胜者的名字，以及一个变量用于存放最高票数。 std::string ans = "***"; // 使用哨兵值来检查是否存在平局。 unsigned long max_vote = 0; // 第一遍遍历：找出所有候选人中的最高票数。 for(const auto &[k, v]: m) { max_vote = std::max(max_vote, v); } // 第二遍遍历：找出获得最高票数的候选人。 for(const auto &[k, v]: m) { if(v == max_vote) { // 如果 'ans' 不再是哨兵值，意味着我们已经找到了一个获胜者。 // 此时再找到一个说明存在平局。 if(ans != "***") { cout << "Runoff!"; return 0; // 在打印平局结果后退出。 } // 这是找到的第一个获得最高票数的候选人。 ans = k; } } // 如果循环完成且 'ans' 只被更新过一次，则打印获胜者的名字。 cout << ans; return 0; } } 题解 这个问题要求我们处理一个投票列表，其中每一票都是一个代表候选人姓名的字符串。我们需要找出得票最多的候选人。如果只有一位候选人得票最高，我们就打印他/她的名字。如果有两位或更多的候选人并列获得最高票数，我们必须宣布“Runoff! ”。投票列表以一个特殊的字符串 *** 结尾。 ...