帮贡排序

GitHub 跳转原题关系图返回列表

先按帮贡和输入顺序给可调整成员重新分配职位，再按职位、等级和输入顺序排序输出。

OJ: luogu

题目 ID: P1786

难度:普及-

标签:排序模拟结构体python

日期: 2026-07-15 21:48

题意

帮派成员有姓名、职位、帮贡和等级。帮主和副帮主职位不能调整；其他人先按帮贡从高到低、输入顺序从前到后排序，重新分配职位。最后按职位高低、等级从高到低、输入顺序从前到后输出。

思路

每个成员用字典保存：

python

1name, role, contribution, level, index

第一阶段：筛出可调整成员，排序关键字为：

python

1(-contribution, index)

然后按名额依次分配 HuFa、ZhangLao、TangZhu、JingYing、BangZhong。

第二阶段：全体成员排序，关键字为：

python

1(role_rank[role], -level, index)

其中 role_rank 表示职位从高到低的顺序。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md：多关键字排序可以用元组作为 key。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：字典适合保存一条记录的多个字段。
数字前加负号可以把升序排序变成降序效果。
Python 排序稳定，但这里显式加入 index 更清楚。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50role_rank = {
    "BangZhu": 0,
    "FuBangZhu": 1,
    "HuFa": 2,
    "ZhangLao": 3,
    "TangZhu": 4,
    "JingYing": 5,
    "BangZhong": 6,
}

new_roles = (
    ["HuFa"] * 2
    + ["ZhangLao"] * 4
    + ["TangZhu"] * 7
    + ["JingYing"] * 25
)

n = int(input())
members = []

for index in range(n):
    name, role, contribution, level = input().split()
    members.append({
        "name": name,
        "role": role,
        "contribution": int(contribution),
        "level": int(level),
        "index": index,
    })

adjustable = [
    member for member in members
    if member["role"] != "BangZhu" and member["role"] != "FuBangZhu"
]
adjustable.sort(key=lambda member: (-member["contribution"], member["index"]))

for rank, member in enumerate(adjustable):
    if rank < len(new_roles):
        member["role"] = new_roles[rank]
    else:
        member["role"] = "BangZhong"

members.sort(key=lambda member: (
    role_rank[member["role"]],
    -member["level"],
    member["index"],
))

for member in members:
    print(member["name"], member["role"], member["level"])

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 115;

int n;

// 成员结构体
struct Member {
    char name[20];    // 姓名
    char role[20];    // 职位
    int  contribution; // 帮贡
    int  level;        // 等级
    int  idx;          // 输入顺序
};

Member members[MAXN];

// 职位对应的排名值（越小职位越高）
int role_rank(char *role) {
    if (strcmp(role, "BangZhu")    == 0) return 0;
    if (strcmp(role, "FuBangZhu")  == 0) return 1;
    if (strcmp(role, "HuFa")       == 0) return 2;
    if (strcmp(role, "ZhangLao")   == 0) return 3;
    if (strcmp(role, "TangZhu")    == 0) return 4;
    if (strcmp(role, "JingYing")   == 0) return 5;
    return 6; // BangZhong
}

// 阶段 1 排序：按帮贡降序，帮贡相同按输入顺序升序
bool cmp1(const Member &a, const Member &b) {
    if (a.contribution != b.contribution)
        return a.contribution > b.contribution;
    return a.idx < b.idx;
}

// 阶段 2 排序：按职位排名升序->等级降序->输入顺序升序
bool cmp2(const Member &a, const Member &b) {
    int ra = role_rank((char*)a.role);
    int rb = role_rank((char*)b.role);
    if (ra != rb) return ra < rb;
    if (a.level != b.level) return a.level > b.level;
    return a.idx < b.idx;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> members[i].name >> members[i].role
            >> members[i].contribution >> members[i].level;
        members[i].idx = i;
    }

    // 新职位分配表
    char new_roles[50][20] = {
        "HuFa", "HuFa",
        "ZhangLao", "ZhangLao", "ZhangLao", "ZhangLao",
        "TangZhu", "TangZhu", "TangZhu", "TangZhu",
        "TangZhu", "TangZhu", "TangZhu",
        "JingYing", "JingYing", "JingYing", "JingYing",
        "JingYing", "JingYing", "JingYing", "JingYing",
        "JingYing", "JingYing", "JingYing", "JingYing",
        "JingYing", "JingYing", "JingYing", "JingYing",
        "JingYing", "JingYing", "JingYing", "JingYing",
        "JingYing", "JingYing", "JingYing", "JingYing",
        "JingYing", "JingYing"
    };
    int new_role_cnt = 38; // 2+4+7+25

    // 筛选出可调整的成员（不是帮主和副帮主）
    Member adj[MAXN];
    int adj_cnt = 0;
    for (int i = 0; i < n; i++) {
        if (strcmp(members[i].role, "BangZhu") != 0 &&
            strcmp(members[i].role, "FuBangZhu") != 0) {
            adj[adj_cnt++] = members[i];
        }
    }

    // 按帮贡排序
    sort(adj, adj + adj_cnt, cmp1);

    // 重新分配职位
    for (int i = 0; i < adj_cnt; i++) {
        if (i < new_role_cnt)
            strcpy(adj[i].role, new_roles[i]);
        else
            strcpy(adj[i].role, "BangZhong");
    }

    // 把调整后的成员合并回原数组
    int p = 0;
    for (int i = 0; i < n; i++) {
        if (strcmp(members[i].role, "BangZhu") == 0 ||
            strcmp(members[i].role, "FuBangZhu") == 0) {
            continue;
        }
        members[i] = adj[p++];
    }

    // 最终排序并输出
    sort(members, members + n, cmp2);

    for (int i = 0; i < n; i++) {
        cout << members[i].name << " "
             << members[i].role << " "
             << members[i].level << "\n";
    }

    return 0;
}

复杂度

成员数最多 110，排序复杂度是 $O(n\log n)$ ，空间复杂度是 $O(n)$ 。

总结

本题是典型的两阶段排序模拟：先重新分配职位，再按展示规则排序。把每个排序规则写成清楚的 key 元组即可。

P1786 帮贡排序

题目背景

帮派名号：星月家园

帮主尊号：Dragonfly Kang

帮派 ID：2685023

帮派等级：4

帮派人数：101/110

帮派技能：（？）

“星月家园”资料，欢迎各位豆友加入 ^_

在 absi2011 的帮派里，死号偏多。现在 absi2011 和帮主等人联合决定，要清除一些死号，加进一些新号，同时还要鼓励帮贡多的人，对帮派进行一番休整。

题目描述

目前帮派内共最多有：

$1$ 位帮主（ $\texttt{BangZhu}$ ）
$2$ 位副帮主（ $\texttt{FuBangZhu}$ ）
$2$ 位护法（ $\texttt{HuFa}$ ）
$4$ 位长老（ $\texttt{ZhangLao}$ ）
$7$ 位堂主（ $\texttt{TangZhu}$ ）
$25$ 名精英（ $\texttt{JingYing}$ ）
若干（数量不限）帮众（ $\texttt{BangZhong}$ ）

保证以上职位是从高到低排列的。

现在 absi2011 要对帮派内几乎所有人的职位全部调整一番。他发现这是个很难的事情。于是要求你帮他调整。

他给你每个人的以下数据：

名字
原来职位
帮贡
等级

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

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

然后更新这些人的职位：

第 $1 \sim 2$ 名：护法
第 $3 \sim 6$ 名：长老
第 $7 \sim 13$ 名：堂主
第 $14 \sim 38$ 名：精英
第 $39 \sim (n-3)$ 名：帮众

可是，乐斗的显示并不按帮贡排序而按职位和等级排序。

他要你按照以下关键字排序并求出最后乐斗显示的列表（在他调整过职位后）：

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

注意：absi2011 无权调整帮主、副帮主的职位，包括他自己的。

输入格式

第一行一个正整数 $n$ ，表示星月家园内帮友的人数。

下面 $n$ 行每行两个字符串两个整数，表示每个人的名字、职位、帮贡、等级。

输出格式

一共输出 $n$ 行，每行包括排序后乐斗显示的名字、职位、等级。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
6
7
8
9
109
DrangonflyKang BangZhu 100000 66
RenZaiJiangHu FuBangZhu 80000 60
absi2011 FuBangZhu 90000 60
BingQiLingDeYanLei HuFa 89000 58
Lcey HuFa 30000 49
BangYou3 ZhangLao 1000 1
BangYou1 TangZhu 100 40
BangYou2 JingYing 40000 10
BangYou4 BangZhong 400 1

输出 #1

text

1
2
3
4
5
6
7
8
9DrangonflyKang BangZhu 66
RenZaiJiangHu FuBangZhu 60
absi2011 FuBangZhu 60
BingQiLingDeYanLei HuFa 58
BangYou2 HuFa 10
Lcey ZhangLao 49
BangYou1 ZhangLao 40
BangYou3 ZhangLao 1
BangYou4 ZhangLao 1

说明/提示

对于 $10\%$ 的数据，保证 $n=3$ 。

对于 $40\%$ 的数据，保证各个人的帮贡均为 $0$ 。

对于 $100\%$ 的数据，保证：

$3\leq n\leq 110$
$1\leq$ 名字长度 $\leq30$
所有名字两两不同
名字只包含 ASCII 可见字符
$0\leq$ 各个人的帮贡 $\leq10^9$
$1\leq$ 各个人等级 $\leq 150$
职位必定为以下七个中的一个：
- $\texttt{BangZhu}$
- $\texttt{FuBangZhu}$
- $\texttt{HuFa}$
- $\texttt{ZhangLao}$
- $\texttt{TangZhu}$
- $\texttt{JingYing}$
- $\texttt{BangZhong}$
初始时帮派内最多有：
- $1$ 位帮主
- $2$ 位副帮主
- $2$ 位护法
- $4$ 位长老
- $7$ 位堂主
- $25$ 名精英
恰好有一名帮主
恰好有两名副帮主
恰好有一名副帮主叫 absi2011

【题目来源】

fight.pet.qq.com

absi2011 授权题目

帮贡排序

目录

题意

思路

Python 知识

代码

复杂度

总结