曾彪彪的个人博客 -- 帮贡排序题解问题总结（论测试用例的重要性）

# 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

```
9
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

```
DrangonflyKang 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 授权题目

这道题第一次提交错误，只得了20分，错误原因有两个：
- 审题不对，对于这段话"注意：absi2011 无权调整帮主、副帮主的职位，包括他自己的。"，我以为是两个条件
  - 无权调整帮助，副帮主的职位
  - 无权调整自己的职位
  其实不是的，第二个条件不用考虑，是我理解偏差，"包括他自己的"意思是：absi2011 是帮助或者副帮主。
  - 第二个错误原因是，没有根据输入序号进行排序，如果不记录每个成员的序号，那么排序可能会不符合预期，所以需要为成员加一个需要。

第一次未通过的代码如下：
```c++
/**
start time: 8:45
End time:
Type: simulator
Solution:
-
Define a struct store name, position, contribution, level
defina a compare, sort by contribution desc.
change the position, keep absi2011 unchanged.
define a compare, sort by position, level desc.
-
-
test case:
- 
input: 
9
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

output:
DrangonflyKang 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
-

input:
10
A BangZhu 100 66
absi2011 FuBangZhu 90000 60
B FuBangZhu 80 60
C HuFa 890 58
D HuFa 30000 49
E ZhangLao 1000 1
F ZhangLao 1000 1
G ZhangLao 2000 1
H ZhangLao 1000 1
I TangZhu 100 40
-
10
A BangZhu 100 66
absi2011 FuBangZhu 90000 60
B FuBangZhu 80 61
C HuFa 890 58
D HuFa 30000 49
E ZhangLao 1000 1
F ZhangLao 1000 1
G ZhangLao 2000 1
H ZhangLao 1000 1
I TangZhu 100 40
-
10
A BangZhu 100 66
absi2011 FuBangZhu 90000 60
B FuBangZhu 80 61
C HuFa 890 58
D HuFa 30000 49
E ZhangLao 1000 1
F ZhangLao 1000 1
G ZhangLao 2000 61
H ZhangLao 1000 1
I TangZhu 100 40
-
10
A BangZhu 100 66
absi2011 FuBangZhu 90000 60
B FuBangZhu 80 61
C HuFa 890 58
D HuFa 30000 49
E ZhangLao 1000 1
F ZhangLao 1000 1
G ZhangLao 2000 62
H ZhangLao 1000 1
I TangZhu 100 40
-
10
A BangZhu 100 66
absi2011 FuBangZhu 90000 60
B FuBangZhu 80 61
C HuFa 890 58
D HuFa 30000 69
E ZhangLao 1000 1
F ZhangLao 1000 1
G ZhangLao 2000 62
H ZhangLao 1000 1
I TangZhu 100 40
-
10
A BangZhu 100 66
absi2011 FuBangZhu 90000 60
B FuBangZhu 80 61
C HuFa 890 58
D HuFa 3000 49
E ZhangLao 1000 1
F ZhangLao 1000 3
G ZhangLao 4000 49
H ZhangLao 1000 2
I TangZhu 100 40
-
10
A BangZhu 100 66
absi2011 FuBangZhu 90000 60
B FuBangZhu 80 61
C HuFa 890 58
D HuFa 3000 49
E ZhangLao 1000 1
F ZhangLao 1000 3
G ZhangLao 3000 49
H ZhangLao 1000 2
I TangZhu 100 40
-
35
A BangZhu 100 66
absi2011 FuBangZhu 90000 60
B FuBangZhu 80 61
C HuFa 890 58
D HuFa 30000 49
E ZhangLao 1000 1
F ZhangLao 1000 1
G ZhangLao 2000 62
H ZhangLao 1000 1
I TangZhu 100 40
J TangZhu 100 40
K TangZhu 100 40
L TangZhu 100 40
M TangZhu 100 4
N TangZhu 100 40
O TangZhu 100 40
P TangZhu 100 40
Q TangZhu 100 40
R TangZhu 100 40
S TangZhu 100 40
T TangZhu 100 40
U TangZhu 100 40
V TangZhu 100 40
W TangZhu 100 40
X TangZhu 100 40
Y TangZhu 100 40
Z TangZhu 100 40
A1 TangZhu 100 40
A2 TangZhu 100 40
A3 TangZhu 100 40
A4 TangZhu 100 40
A5 TangZhu 100 40
A6 TangZhu 300 40
A7 TangZhu 109 40
A8 TangZhu 100 400
-
first submit score: 100
cause:

**/

#include <bits/stdc++.h>
using namespace std;

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

vector<string> positions = {"", "BangZhong", "JingYing", "TangZhu", "ZhangLao", "HuFa", "FuBangZhu", "BangZhu"};
unordered_map<string, int> positionMap;
vector<Member> memberList;
vector<int> positionSequence = {7, 6, 6, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1};

bool compareByContribution(Member &a, Member &b)
{
    return a.contribution > b.contribution;
}

bool compareByPosition(Member &a, Member &b)
{
    if (a.position == b.position)
    {
        return a.level > b.level;
    }
    return a.position > b.position;
}

int main()
{
    // freopen("C:/Users/zengsam/Downloads/P1042_2.in", "r", stdin);
    for (int i = 0; i < positions.size(); i++)
    {
        positionMap[positions[i]] = i;
    }
    int n;
    cin >> n;
    string absi2011Name = "absi2011";
    while (n--)
    {
        Member m;
        cin >> m.name;
        string p;
        cin >> p;
        m.position = positionMap[p];
        cin >> m.contribution;
        cin >> m.level;
        memberList.push_back(m);
    }
    sort(memberList.begin() + 3, memberList.end(), compareByContribution);    
    for (int i = 0; i < memberList.size(); i++)
    {
        memberList[i].position = (i < positionSequence.size() ? positionSequence[i] : 1);
    }
    sort(memberList.begin(), memberList.end(), compareByPosition);

cout << "===========" << endl;

for (auto m : memberList)
    {
        cout << m.name << " " << positions[m.position] << " " << m.level << endl;
    }

return 0;
}

```

这题做错的主要原因，是没有根据输入序号进行排序，这里还是缺少了测试用例。我只拿官方的测试用例验证，但是数据多一点，比如名字有A A1 A2等时，排序就会不符合预期，需要未结构体增加一个id字段，记录输入的id，也根据id进行排序，问题解决。

帮贡排序题解问题总结（论测试用例的重要性）

评论(0)