时间戳

首页 > 技术文章 > 洛谷 P1786 帮贡排序 题解

洛谷 P1786 帮贡排序 题解

acioi 2019-11-04 11:07 原文

P1786 帮贡排序

题目背景

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

题目描述

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

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

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

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

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

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

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

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

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #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

说明/提示

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

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

另： 帮派名号：星月家园

帮主尊号：Dragonfly Kang

帮派ID：2685023

帮派等级：4

帮派人数：101/110

帮派技能：

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

【数据范围】

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

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

对于100%的数据，保证3<=n<=110,各个名字长度<=30,0<=各个人的帮贡<=1000000000

1<=各个人等级<=150

保证职位必定为BangZhu,FuBangZhu,HuFa,ZhangLao,TangZhu,JingYing,BangZhong之间一个

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

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

保证名字不重复。

【题目来源】

fight.pet.qq.com

absi2011授权题目

【思路】

模拟，排序

【题目大意】

根据题目中给出的条件赋予职位
然后排序

【题目分析】

排序这是很显然的，但是一道绿题不可能让你一个sort就水过去吧？
不过也不可能出什么恶心的数据结构来，毕竟只是一道绿题。
所以难度只会存在于排序的条件
也就是到底什么样的才应该在前面

【排序条件】

无权调动帮主，副帮主和自己
所以帮主，副帮主和自己是不需要挪动的
然后就看排序的顺序了
需要两次排序
第一次是为了给予职位，第二次是为了输出

  1. 给予职位是按照帮贡来给
    还有如果有相同帮贡但是职位不够的话原来当的应该继续当
    这不需要考虑
    因为原来当的一开始读入就在前面
    sort排序的时候只要不在cmp里面加上个=就会按照原来当的在前面排序
    这样就能保证原来当的优先当了

  2. 职位是第一要素这很显然
    等级是第二关键字
    所以要先按照职位排序
    然后如果职位相同那就把等级高的放在前面
    再就是职位相同等级也相同的话
    那原来在前面的就还在前面
    这点不需要考虑
    因为如果用sort的话
    只要cmp里面自定义排序方式写正确了那就没有问题
    （这里的正确很大可能是不需要=，主要是看你怎么写）

【完整代码】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
map<string,int>s;
const int Max = 120;
struct node
{
	string name,zhiwei;//名字，职位 
	int bg,dg;//帮贡，等级 
	int zz;//一开始给出数据中所在的位置 
}a[Max];

bool cmp(const node x,const node y)//帮贡排序 
{
	if(x.bg == y.bg)
		return x.zz < y.zz; 
	return x.bg > y.bg; 
}

bool cmp1(const node x,const node y)//输出排序
{
	if(s[x.zhiwei] == s[y.zhiwei])
	{
		if(x.dg == y.dg)
			return x.zz < y.zz;
		return x.dg > y.dg;
	}
	else
		return s[x.zhiwei] < s[y.zhiwei]; 
}

int main()
{
	s["BangZhu"] = 1,s["FuBangZhu"] = 2,s["HuFa"] = 3,s["ZhangLao"] = 4,
	s["TangZhu"] = 5,s["JingYing"] = 6,s["BangZhong"] = 7;
	int n;
	cin >> n;
	for(register int i = 1;i <= n;++ i)
		cin >> a[i].name >> a[i].zhiwei >> a[i].bg >> a[i].dg,a[i].zz = i; 
	int js = 0;
	sort(a + 4,a + 1 + n,cmp);
	int jj = 1;
	for(register int i = 1;i <= n;++ i)
	{
		if(a[i].zhiwei != "BangZhu" && a[i].zhiwei != "FuBangZhu")
		{
			if(jj >= 1 && jj <= 2)
				a[i].zhiwei = "HuFa";
			if(jj >= 3 && jj <= 6)
				a[i].zhiwei = "ZhangLao";
			if(jj >= 7 && jj <= 13)
				a[i].zhiwei = "TangZhu";
			if(jj >= 14 && jj <= 38)
				a[i].zhiwei = "JingYing";
			if(jj >= 39)
				a[i].zhiwei = "BangZhong";
			jj ++;
		}
	}
	sort(a + 1,a + 1 + n,cmp1); 
	for(register int i = 1;i <= n;++ i)
		cout << a[i].name << " " << a[i].zhiwei << " " << a[i].dg << endl;
	return 0;
}

推荐阅读