2024 - 10 - 13 - 30 篇 - C++、模拟算法、洛谷、蓝桥
作者(Author): 郑龙浩 / 仟濹(CSDN 账号名)
【模拟算法】洛谷P1786 - 帮贡排序
1. 题干：
目前帮派内共最多有一位帮主，两位副帮主，两位护法，四位长老，七位堂主，二十五名精英，帮众若干。
现在absi2011要对帮派内几乎所有人的职位全部调整一番。他发现这是个很难的事情。于是要求你帮他调整。
他给你每个人的以下数据：他的名字（长度不会超过30），他的原来职位，他的帮贡，他的等级。
他要给帮贡最多的护法的职位，其次长老，以此类推。
可是，乐斗的显示并不按帮贡排序而按职位和等级排序。
他要你求出最后乐斗显示的列表(在他调整过职位后)：职位第一关键字，等级第二关键字。
注意：absi2011无权调整帮主、副帮主的职位，包括他自己的（这不是废话么…）
他按原来的顺序给你（所以，等级相同的，原来靠前的现在也要靠前，因为经验高低的原因，但此处为了简单点省去经验。）
输入输出格式
输入格式
第一行一个正整数n，表示星月家园内帮友的人数。
下面n行每行两个字符串两个整数，表示每个人的名字、职位、帮贡、等级。
输出格式
一共输出n行，每行包括排序后乐斗显示的名字、职位、等级。
输入输出样例
输入样例
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输出样例
输出样例
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代码
2. 我的唠叨：
此题用了我好久的时间才做出来
原先我写的代码使用的函数过多，我想把一些很细的地方也用函数写出来，虽然实现了模块化，但是复杂度增加了，并且极大的增加了出错误的概率，并且改错也不是很好改。所以后来还是决定将函数去掉，写到main函数中去吧。
比如之前想把下面这个代码变为函数
for( int i = 1; i <= num; i ++ ){
if( i == 1 ) data[ i ].jobs = "BangZhu";
else if( i == 2 || i == 3 ) data[ i ].jobs = "FuBangZhu";
else if( i == 4 || i == 5 ) data[ i ].jobs = "HuFa";
else if( i >= 6 && i <= 9 ) data[ i ].jobs = "ZhangLao";
else if( i >= 10 && i <= 16 ) data[ i ].jobs = "TangZhu";
else if( i >= 17 && i <= 41 ) data[ i ].jobs = "JingYing";
else data[ i ].jobs = "BangZhong";
}
其实做了好久，主要是总是会有一些地方不小心就写错了，测试点总是不完全对。
而这个做题思路是在洛谷题解看了某位大佬才会的。
题解的链接：https://www.luogu.com.cn/problem/solution/P1786
3. 思路：
-
定义、输入(人员数量、人员信息)
-
第一次排序 –> 【帮贡】第一关键字，【输入顺序（隐含条件）】第二关键字
- 若【帮贡】相同，按照【输入顺序n】排序 –> 【输入顺序n】小的在前
- 若【帮贡】不同，按照【帮贡】大小排序 – > 帮贡大的在前
-
第二次排序 –> 【职务】第一关键字，【等级】第二关键字，【输入顺序(隐含条件)】第三关键字
-
若【职务】相同 && 【等级】相同，则按照【输入顺序n】排序 –> n 小的在前
-
若【职务】相同 && 【等级】不同，则按照【等级】排序 –> 【等级】大的在前
-
若【职务】不同，则按照【职务】排序 –> 【职务】牛的在前
关于这个地方就要注意了，因为职务是字符串，所以不能直接比较，不然比较的就是字符串的字母顺序了，所以要自己单数写一个change函数，将【职务】进行【数字化】，这样就可以将【职务】转为【数字】进行比较了
-
-
打印 人员信息
下面是正确的代码：
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
// 存储人员信息
struct ddd{
string name, jobs;
long long bg;
int grade, n;
};
// 将职务 -> 数字的转换函数 -- > 为了在排序时用职位进行排序
int change( string a){
if( a == "BangZhu" ) return 0;
if( a == "FuBangZhu" ) return 1;
if( a == "HuFa" ) return 2;
if( a == "ZhangLao" ) return 3;
if( a == "TangZhu" ) return 4;
if( a == "JingYing" ) return 5;
if( a == "BangZhong" ) return 6;
return -1;
}
// 第1个排序的【比较函数】
int campare_1( ddd a, ddd b ){
if( a.bg == b.bg ) return a.n < b.n; // 若【帮贡】相等，按照【输入顺序】排序 --> n 小的在前
else return a.bg > b.bg; // 若【帮贡】不相等，按照【帮贡】降序排序 --> 帮贡大的在前
}
// 第2个排序的【比较函数】
int campare_2( ddd a, ddd b ){
if( change( a.jobs ) == change( b.jobs ) )
if( a.grade == b.grade ) return a.n < b.n; // 若【职务】相等&&【等级】相等，按照【输入顺序n】排序 --> n 小的在前
else return a.grade > b.grade; // 若【职务】相等&&【等级】不等，按照【等级】降序排序 --> 等级高的在前
else return change( a.jobs ) < change( b.jobs ); // 若【职务】不相等，按照【职务】升序排序 --> 职务低的在前
}
// 打印 人员信息
void print_da( ddd *data, int num ){
for( int i = 1; i <= num; i ++ ){
cout << data[ i ].name << " " << data[ i ].jobs << " " << data[ i ].grade << endl;
}
}
int main( void ){
ddd data[ 120 ];// 存储人员信息
int num; // 人数
cin >> num; // 输入 人数
for( int i = 1; i <= num; i ++ ){ // 输入 人员信息
cin >> data[ i ].name >> data[ i ].jobs >> data[ i ].bg >> data[ i ].grade;
data[ i ].n = i;
}
// 第一次排序 -->
// 按照【帮贡】降序排序 --> 【帮贡】大的在前
// 若【帮贡】相等，按照【输入顺序】排序 --> 【输入顺序n】 小的在前
sort ( data + 4, data + num + 1, campare_1 );
// 对排序后的信息进行重新授予【职务】
for( int i = 1; i <= num; i ++ ){
if( i == 1 ) data[ i ].jobs = "BangZhu";
else if( i == 2 || i == 3 ) data[ i ].jobs = "FuBangZhu";
else if( i == 4 || i == 5 ) data[ i ].jobs = "HuFa";
else if( i >= 6 && i <= 9 ) data[ i ].jobs = "ZhangLao";
else if( i >= 10 && i <= 16 ) data[ i ].jobs = "TangZhu";
else if( i >= 17 && i <= 41 ) data[ i ].jobs = "JingYing";
else data[ i ].jobs = "BangZhong";
}
// 第二次排序 -->
// 按照【职务】升序排序 --> 【职务】牛逼的在前(change 函数返回的值越小，则证明【职务】越牛逼)
// 若【职务】相等，按照【等级】降序排序 --> 【等级】高的在前
// 若【职务】和【等级】都相等，按照【输入顺序n】排序 --> 【输入顺序n】 小的在前
sort ( data + 1, data + num + 1, campare_2 );
// 打印 人员信息
print_da( data, num );
return 0;
}
