P1786 帮贡排序——题解

解题思路

先记录每个人的输入序号。筛出帮主、副帮主以外的成员，按帮贡和输入序号排序并按名次修改职位。然后把所有成员按职位等级、人物等级和输入序号进行第二次排序，依次输出。

复杂度分析

两次排序均为 $O(n\log n)$，空间复杂度 $O(n)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
struct P{string name,pos;long long gong;int level,id,rank;};
int rk(const string&s){
    if(s=="BangZhu")return 1;if(s=="FuBangZhu")return 2;if(s=="HuFa")return 3;
    if(s=="ZhangLao")return 4;if(s=="TangZhu")return 5;if(s=="JingYing")return 6;return 7;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;cin>>n;vector<P>a(n);vector<int> v;
    for(int i=0;i<n;i++){
        cin>>a[i].name>>a[i].pos>>a[i].gong>>a[i].level;a[i].id=i;
        if(a[i].pos!="BangZhu"&&a[i].pos!="FuBangZhu") v.push_back(i);
    }
    sort(v.begin(),v.end(),[&](int x,int y){return a[x].gong!=a[y].gong?a[x].gong>a[y].gong:a[x].id<a[y].id;});
    for(int i=0;i<(int)v.size();i++){
        if(i<2)a[v[i]].pos="HuFa";
        else if(i<6)a[v[i]].pos="ZhangLao";
        else if(i<13)a[v[i]].pos="TangZhu";
        else if(i<38)a[v[i]].pos="JingYing";
        else a[v[i]].pos="BangZhong";
    }
    sort(a.begin(),a.end(),[](const P&x,const P&y){
        int rx=rk(x.pos),ry=rk(y.pos);
        if(rx!=ry)return rx<ry;
        if(x.level!=y.level)return x.level>y.level;
        return x.id<y.id;
    });
    for(auto &x:a) cout<<x.name<<' '<<x.pos<<' '<<x.level<<'\n';
    return 0;
}

#include <bits/stdc++.h> using namespace std; struct P{string name,pos;long long gong;int level,id,rank;}; int rk(const string&s){ if(s=="BangZhu")return 1;if(s=="FuBangZhu")return 2;if(s=="HuFa")return 3; if(s=="ZhangLao")return 4;if(s=="TangZhu")return 5;if(s=="JingYing")return 6;return 7; } int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int n;cin>>n;vector

a(n);vector v; for(int i=0;i<n;i++){ cin>>a[i].name>>a[i].pos>>a[i].gong>>a[i].level;a[i].id=i; if(a[i].pos!="BangZhu"&&a[i].pos!="FuBangZhu") v.push_back(i); } sort(v.begin(),v.end(),[&](int x,int y){return a[x].gong!=a[y].gong?a[x].gong>a[y].gong:a[x].id<a[y].id;}); for(int i=0;i<(int)v.size();i++){ if(i<2)a[v[i]].pos="HuFa"; else if(i<6)a[v[i]].pos="ZhangLao"; else if(i<13)a[v[i]].pos="TangZhu"; else if(i<38)a[v[i]].pos="JingYing"; else a[v[i]].pos="BangZhong"; } sort(a.begin(),a.end(),[](const P&x,const P&y){ int rx=rk(x.pos),ry=rk(y.pos); if(rx!=ry)return rx<ry; if(x.level!=y.level)return x.level>y.level; return x.id<y.id; }); for(auto &x:a) cout<<x.name<<' '<<x.pos<<' '<<x.level<<'\n'; return 0; }