洛谷：P1786：帮贡排序

题目

P1786：帮贡排序

分析

这是一道结合了模拟和排序的题目，适合进行综合练习。

帮众的结构

首先根据输入来分析一个帮众的基本信息：名字、职位、贡献、等级。所以，这个帮众的结构至少要有这么四个属性。同时，我们还注意到，在题目中两次提到：“在输入中出现的顺序（从前到后）”。这个信息并未显式提供，但是我们可以在循环读入帮众信息的时候，根据循环变量来赋值。这个信息显然也是帮众的一个属性。最终的一个帮众就有五个属性。

struct Member
{
    string name;
    string position;
    int contribution;
    int level;
    int original_pos;
};

两个排序

题目中有两个排序。

排序一

按照以下关键字给帮派内的人（帮主、副帮主除外）按以下关键字排序

• 帮贡（从高到低）第一关键字
• 在输入中出现的顺序（从前到后）第二关键字

这个比较直观，是一个经典的结构排序。

bool sortByContribution(const Member& a, const Member& b)
{
    if (a.contribution != b.contribution)
    {
        return a.contribution > b.contribution;
    }
    return a.original_pos < b.original_pos;
}

排序二

在分配完新职位后，需要重新排序。排序标准是：

• 职位（从高到低）第一关键字
• 等级（从高到低）第二关键字
• 在输入中出现的顺序（从前到后）第三关键字

同样，这也是一个结构排序：

bool sortByRank(const Member& a, const Member& b)
{
    if (posRank[a.position] != posRank[b.position])
    {
        return posRank[a.position] < posRank[b.position];  // 职位高的排前面
    }
    if (a.level != b.level)
    {
        return a.level > b.level;  // 等级高的排前面
    }
    return a.original_pos < b.original_pos;  // 等级相同时，原来靠前的排前面
}

// 定义职位及其对应的优先级（数字越小优先级越高）
map<string, int> posRank = {{"BangZhu", 1},  {"FuBangZhu", 2}, {"HuFa", 3},
                            {"ZhangLao", 4}, {"TangZhu", 5},   {"JingYing", 6},
                            {"BangZhong", 7}};

分配职位

由于我们不能调整帮主、副帮主的职位，所以要分开处理。处理的方式是，帮主、副帮主先放在一边，用retain数组保存，而其他人用change保存。

对于change数组，我们还要跟踪每个职位可以有的人数：

// 定义各职位的最大人数
map<string, int> posLimit =
    {
        {"BangZhu", 1},        {"FuBangZhu", 2}, {"HuFa", 2},
        {"ZhangLao", 4},       {"TangZhu", 7},   {"JingYing", 25},
        {"BangZhong", INT_MAX}  // 帮众没有人数限制
};

在重新分配时，显然先要分配“护法”，然后是“长老”、“堂主”等。所以，这是一个顺序的if...else if...过程：

for (auto& m : change)  // Use reference to modify original
{
    if (Hufa < posLimit["HuFa"])
    {
        m.position = "HuFa";
        Hufa++;
    }
    else if (Zhanglao < posLimit["ZhangLao"])
    {
        m.position = "ZhangLao";
        Zhanglao++;
    }
    // ...
    else
    {
        m.position = "BangZhong";
    }
}

重新分配完毕后，调用前面的“排序二”，然后按要求输出即可。

答案

思考

需要注意**比较器的严格性与稳定性。

• 排序一：先按帮贡降序，再按 original_pos 升序；
• 排序二：先按职位等级（高→低），再按等级（高→低），再按 original_pos 升序；

比较器应满足“严格弱序”且覆盖所有并列情况，避免依赖未声明的稳定性。若希望保留原相对顺序，可使用stable_sort搭配明确的次关键字。