P4624 选票统计（入门）

解题思路

这道题和"候选人的得票数"有点像，但输出方式不同：这次要按得票数从高到低输出。分四步做。

第一步，明确任务。 三位候选人 li、zhang、sun，n 个选民每人投一票。先统计每位候选人各得多少票，再按票数从高到低输出"姓氏 票数"。

第二步，用结构体和 strcmp 计数。 结构体 Candidate 保存候选人的姓氏和得票数，数组初始化为三位候选人的名字和 0 票。读入一张选票时，用 strcmp 把它和三位候选人的姓氏逐一比较：逐字符完全相同就说明投给了这位，把对应票数加一。"li""zhang""sun"一个字符都不能拼错，否则会统计错人。strcmp 就像一字一句地对答案，只有每个字符都一样才相等，所以用它做精确比较最可靠，比直接比较字符数组稳妥得多。

第三步，按票数从高到低排序。 统计完成后，用 sort() 按票数从高到低排好，再依次输出。题目保证三位候选人的票数都不相同，排序结果唯一，不会出现并列。

第四步，用一个例子检验。 比如输入 10 张选票，sun 出现 5 次、li 出现 3 次、zhang 出现 2 次，排序后依次输出 sun 5、li 3、zhang 2，票数最多的排最前面。注意我们只统计出现次数，不关心投票先后，所以输入顺序打乱也没关系。

**回顾总结。**这道题是"统计加排序"两件套：结构体数组初始化时，花括号里挨个写上名字和 0 票，顺序正好对应下标 0、1、2。先用 strcmp 精确统计每人票数，再用 sort() 按票数降序输出。和"候选人的得票数"不同，那边按固定顺序输出，这边按票数排序输出，读题时一定要分清。

参考代码

// 用途：统计三位候选人的票数，并按得票数从高到低输出姓氏和票数。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

struct Candidate {
    char name[10];      // 候选人的姓氏
    int votes;          // 候选人的得票数
};

// 排序规则：得票数高的排前面
bool cmp(const Candidate &a, const Candidate &b) {
    return a.votes > b.votes;
}

int main() {
    int n;                                          // 选民人数
    cin >> n;                                       // 读入选民人数
    Candidate cand[3] = { {"li", 0}, {"zhang", 0}, {"sun", 0} };  // 三位候选人

    for (int i = 0; i < n; i++) {                   // 读入每张选票
        char ballot[10];                            // 当前选票上的姓氏
        cin >> ballot;                              // 读入当前选票
        for (int j = 0; j < 3; j++) {               // 依次查找投给哪位候选人
            if (strcmp(ballot, cand[j].name) == 0) cand[j].votes++;  // 相同则加一
        }
    }
    sort(cand, cand + 3, cmp);   // 按得票数从高到低排序

    for (int i = 0; i < 3; i++) {                   // 输出三位候选人的结果
        cout << cand[i].name << ' ' << cand[i].votes << '\n';  // 姓氏和票数
    }
    return 0;                                       // 程序结束
}

复杂度分析

读 n 张选票，每张最多比较 3 次，时间复杂度 O(n)，n 最大 100。排序只有 3 个元素，可以忽略不计。额外空间 O(1)。注意输入里候选人的姓氏出现的顺序是打乱的，我们只统计出现次数，不关心投票先后；三位候选人数组在初始化时就写好了名字，之后只需要更新票数，最后按票数排序即可。字符串比较函数 strcmp 在 头文件里，用之前要先 include，它会逐字符比较两个字符串并返回大小关系。