6.帮贡排序

题目链接：[P1786 帮贡排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)]()

题目背景

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

题目描述

目前帮派内共最多有一位帮主，两位副帮主，两位护法，四位长老，七位堂主，二十五名精英，帮众若干。

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

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

他的名字（长度不会超过 \(30\)），他的原来职位，他的帮贡，他的等级。

他要给帮贡最多的护法的职位，其次长老，以此类推。

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

他要你求出最后乐斗显示的列表(在他调整过职位后)：职位第一关键字，等级第二关键字。

注意：absi2011 无权调整帮主、副帮主的职位，包括他自己的（这不是废话么..）

他按原来的顺序给你（所以，等级相同的，原来靠前的现在也要靠前，因为经验高低的原因，但此处为了简单点省去经验。）

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

<code>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

提示

各种职位用汉语拼音代替。

如果职位剩 \(1\) 个，而有 \(2\) 个帮贡相同的人，则选择原来在前的现在当选此职位。

另：

帮派名号：星月家园

帮主尊号：Dragonfly Kang

帮派ID：2685023

帮派等级：4

帮派人数：101/110

帮派技能：

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

【数据范围】

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

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

对于 \(100\%\) 的数据，保证 \(3\leq n\leq 110\)，各个名字长度\(\leq30\)，\(0\leq\) 各个人的帮贡 \(\leq1000000000\)，

\(1\leq\) 各个人等级 \(\leq 150\)。

保证职位必定为 \(\texttt{BangZhu}\)，\(\texttt{FuBangZhu}\)，\(\texttt{HuFa}\)，\(\texttt{ZhangLao}\)，\(\texttt{TangZhu}\)，\(\texttt{JingYing}\)，\(\texttt{BangZhong}\) 之中的一个

保证有一名帮主，保证有两名副帮主，保证有一名副帮主叫 absi2011

不保证一开始帮派里所有职位都是满人的，但排序后分配职务请先分配高级职位。例如原来设一名护法现在设两名。

保证名字不重复。

【题目来源】

fight.pet.qq.com

absi2011 授权题目

思路：

• 这题我们首先捋清楚思路，我们首先得对帮派中的所有人先分配新的职位，然后根据新的职位，等级和编号进行重新排序后输出

对所有人分配新的职位：

• 按照题目给出的条件，我们对所有人进行重新分配职位：帮主，副帮主不需要重新分配职位，但是对于下面的人，我们需要先看帮贡是否相同，不同的话就帮贡大的人排前面，否则比较序号，序号小的人排在前面，并且我们只需要从护法开始排序（因为我们数组是从下标1开始计数，所以说我们只需要从a+4------a+1+n排序即可）。

• 定义结构体和结构体数组

struct people {

//原先的职位，名字，和新职位

string name, zhiwei,xzw;

//帮贡一定得开long long

long long banggong;

long long dengji;

int num;

}a[125];

int n;

• 按照帮贡来排序，帮贡相同时按序号排序

bool compare(people p1, people p2)

{

if (p1.banggong != p2.banggong) return p1.banggong>p2.banggong;

else return p1.num<p2.num;

}

• 按照帮贡排序,并分配新的职位

//排序，排护法及其后面的所有人

sort(a + 4, a + 1 + n, compare);

for (int i = 1; i <= n; i++) {

if (i == 1) a[i].xzw = "BangZhu";

else if (i >= 2 && i <= 3) a[i].xzw = "FuBangZhu";

else if (i >= 4 && i <= 5) a[i].xzw = "HuFa";

else if (i >= 6 && i <= 9) a[i].xzw = "ZhangLao";

else if (i >= 10 && i <= 16) a[i].xzw = "TangZhu";

else if (i >= 17 && i <= 41) a[i].xzw = "JingYing";

else a[i].xzw = "BangZhong";

}

• 定义新的比较函数，用于排序输出位置的函数，但是，我们得知道，怎么去按照职位排序呢？————我们可以定义一个函数，职位高的就返回数字大的，比较它们返回的数字即可

//将职位转化为数字，方便根据职位来划分顺序,职位越大，数字越大

int change(string s)

{

if (s == "BangZhu") return 6;

else if (s == "FuBangZhu") return 5;

else if (s == "HuFa") return 4;

else if (s == "ZhangLao") return 3;

else if (s == "TangZhu") return 2;

else if (s == "JingYing") return 1;

else return 0;

}

对新的所有人进行顺序上的排序

bool compare2(people p1, people p2)

{

if (change(p1.xzw) != change(p2.xzw)) return change(p1.xzw) > change(p2.xzw);

else {

if (p1.dengji != p2.dengji) return p1.dengji > p2.dengji;

else {

return p1.num < p2.num;

}

}

}

最终代码

#include<iostream>

#include<algorithm>

using namespace std;

struct people {

string name, zhiwei, xzw;

long long banggong;

long long dengji;

int num;

}a[125];

int n;

bool compare(people p1, people p2)

{

if (p1.banggong == p2.banggong) return p1.num < p2.num;

else return p1.banggong > p2.banggong;

}

//将职位转化为数字，方便根据职位来划分顺序,职位越大，数字越大

int change(string s)

{

if (s == "BangZhu") return 6;

else if (s == "FuBangZhu") return 5;

else if (s == "HuFa") return 4;

else if (s == "ZhangLao") return 3;

else if (s == "TangZhu") return 2;

else if (s == "JingYing") return 1;

else return 0;

}

bool compare2(people p1, people p2)

{

if (change(p1.xzw) != change(p2.xzw)) return change(p1.xzw) > change(p2.xzw);

else {

if (p1.dengji != p2.dengji) return p1.dengji > p2.dengji;

else {

return p1.num < p2.num;

}

}

}

int main()

{

cin >> n;

for (int i = 1; i <= n; i++) {

cin >> a[i].name >> a[i].zhiwei >> a[i].banggong >> a[i].dengji;

a[i].num = i;

}

//排序，排护法及其后面的所有人

sort(a + 4, a + 1 + n, compare);

for (int i = 1; i <= n; i++) {

if (i == 1) a[i].xzw = "BangZhu";

else if (i >= 2 && i <= 3) a[i].xzw = "FuBangZhu";

else if (i >= 4 && i <= 5) a[i].xzw = "HuFa";

else if (i >= 6 && i <= 9) a[i].xzw = "ZhangLao";

else if (i >= 10 && i <= 16) a[i].xzw = "TangZhu";

else if (i >= 17 && i <= 41) a[i].xzw = "JingYing";

else a[i].xzw = "BangZhong";

}

//再排一次序

sort(a + 1, a + 1 + n, compare2);

for (int i = 1; i <= n; i++) {

cout << a[i].name << " " << a[i].xzw << " " << a[i].dengji << endl;

}

return 0;

}