题意分析

• 投票制度：澳大利亚投票制度（Instant-Runoff Voting），采用多轮淘汰制，每轮统计当前有效选票的第一选择。
• 候选人：共有$n$个候选人（$n \leq 20$），姓名可能包含任意可打印字符（长度$\leq 80$）。
• 选票格式：每张选票是$1$到$n$的一个排列，表示选民对候选人的优先级排序。
• 获胜条件：
  • 某候选人获得**超过$50\%$**的当前有效选票，直接当选。
  • 若所有候选人得票相同，则全部平局输出。

解题思路

1. 数据结构设计

• 候选人列表：用数组或链表存储候选人姓名及其当前得票状态。
• 选票池：存储所有选票的优先级列表，并动态更新每张选票的当前有效选择。

2. 投票流程模拟

初始轮次

• 统计每张选票的第一选择，计算各候选人得票数。
• 检查是否有候选人得票超过$50\%$（即$\text{得票数} > \lfloor \frac{\text{总票数}}{2} \rfloor$）。

淘汰轮次

• 若无候选人胜出，则淘汰所有得票最低的候选人（注意可能多人并列最低）。
• 对每张选票：
  • 若其当前有效候选人被淘汰，则将其票转移给下一个未被淘汰的候选人。
• 重新统计得票，重复检查胜出条件。

3. 终止条件

• 某候选人得票超过$50\%$：输出其姓名。
• 所有候选人得票相同：按输入顺序输出所有候选人姓名。

4. 关键实现细节

• 选票的当前有效选择：需动态维护每张选票的最高优先级未淘汰候选人。
• 淘汰多人情况：一轮可能淘汰多个得票并列最低的候选人。
• 平局处理：所有候选人得票相同时需立即终止并输出结果。

5. 复杂度分析

• 时间：最多$n$轮淘汰，每轮遍历所有选票（$1000$张），总复杂度$O(n \times 1000 \times n) = O(20 \times 1000 \times 20) = O(4 \times 10^5)$，完全可行。
• 空间：存储选票和候选人信息，空间复杂度$O(20 + 1000 \times 20) = O(20020)$。

标程

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 20 + 1;
const int N2 = 80;
const int N3 = 1000;
char name[N + 1][N2 + 1];
int vote[N3][N];
int out[N], cnt[N];
char s[1024];

int main()
{
    int n;
    while (~scanf("%d%*c", &n)) {
        for (int i = 1; i <= n; i++) gets(name[i]);

        int num = 0;    // 投票人数
        while (gets(s) && s[0]) {
            int a = 0, cnt = 0;
            for (int i = 0; s[i]; i++)
                if (isdigit(s[i])) {
                    a *= 10;
                    a += s[i] - '0';
                } else {
                    vote[num][cnt++] = a;
                    a = 0;
                }
            vote[num++][cnt++] = a;
        }

        // 手动初始化 out 数组
        for (int i = 0; i < N; ++i) {
            out[i] = 0;
        }

        int flag = 0, res = n, tot = 0;
        while (res > 1) {
            tot = 0;
            // 手动初始化 cnt 数组
            for (int i = 0; i < N; ++i) {
                cnt[i] = 0;
            }
            for (int i = 0; i < num; i++)
                for (int j = 0; j < n; j++)
                    if (out[vote[i][j]] == 0) {
                        cnt[vote[i][j]]++, tot++;
                        break;
                    }
            for (int i = 1; i <= n; i++)
                if (cnt[i] * 2 > tot && out[i] == 0) {
                    printf("%s\n", name[i]);
                    flag = 1;
                    break;
                }
            if (flag) break;
            int minc = N3 + 1, maxc = 0;
            for (int i = 1; i <= n; i++)
                if (out[i] == 0)
                    minc = min(minc, cnt[i]), maxc = max(maxc, cnt[i]);
            if (minc == maxc) break;
            for (int i = 1; i <= n; i++)
                if (cnt[i] == minc) out[i] = 1, res--;
        }

        if (!flag) {
            for (int i = 1; i <= n; i++)
                if (out[i] == 0) printf("%s\n", name[i]);
        }
    }

    return 0;
}