C++竞赛编程：奖品分配问题的算法解析与优化

1. 2023年12月GESP真题解析：C++八级奖品分配问题

作为一名长期从事信息学竞赛教学的老师，我发现奖品分配这类题目在各类编程竞赛中频繁出现。这类题目不仅考察学生的编程基本功，更能检验他们解决实际问题的能力。今天我们就来详细拆解这道GESP八级考题，我会从题目理解、算法设计到代码实现，带大家完整走一遍解题流程。

1.1 题目描述与需求分析

题目描述：班级有N名同学，学号从0到N-1。期末考试后，老师需要根据成绩分配M件奖品。分配规则如下：

1. 按成绩从高到低排序
2. 成绩相同则学号小的优先
3. 从排名最高的开始，轮流分配奖品直到发完

我们需要编写程序，输入同学数量N、奖品数量M和每个同学的成绩，输出每个同学最终获得的奖品数量。

这个问题的核心在于：

• 处理排序规则（主排序键：成绩降序；次排序键：学号升序）
• 实现循环分配逻辑（类似轮询机制）
• 高效处理大规模数据（考虑时间复杂度）

1.2 数据结构选择与算法设计

面对这个问题，我们需要选择合适的数据结构和算法：

数据结构选择：

cpp复制struct Student {
    int id;
    int score;
    int prize = 0; // 初始奖品数为0
};

使用结构体存储学生信息比分开维护多个数组更清晰，也更容易进行排序操作。特别是当题目复杂度增加时（比如后续需要添加更多属性），结构体的优势会更加明显。

算法流程：

1. 输入学生数据
2. 按照规则排序
3. 轮询分配奖品
4. 输出结果

排序部分可以直接使用STL的sort函数，但需要自定义比较器。奖品分配则可以采用循环取模的方式实现。

1.3 核心代码实现

让我们看下关键部分的代码实现：

自定义比较函数：

cpp复制bool compare(const Student &a, const Student &b) {
    if(a.score != b.score) 
        return a.score > b.score; // 成绩高的在前
    return a.id < b.id; // 成绩相同时学号小的在前
}

奖品分配逻辑：

cpp复制void distributePrizes(vector<Student> &students, int M) {
    int index = 0;
    while(M > 0) {
        students[index % students.size()].prize++;
        M--;
        index++;
    }
}

这里使用取模运算实现循环分配，避免了复杂的循环控制。每次都给当前index位置的学生分配一个奖品，然后index++，当index超过学生数量时会自动回绕。