题解：P11185 奖牌排序

· · 题解

B. 奖牌排序 (medal) 官方题解

本题考察的主要知识点有：

45 分做法

对于每个小朋友，如果以金牌数排序，如果有 k 个人金牌比他多，那么这个小朋友的排名是 k+1。用同样的原理可以计算出按照银牌或铜牌数排序时这个小朋友的排名。输出时，取三个排名中最靠前的即可。时间复杂度为 O(n^2)，可以通过前 9 个测试点。

#include<bits/stdc++.h>
using namespace std;
int n,g[200005],s[200005],b[200005];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&g[i],&s[i],&b[i]);
    for(int i=1;i<=n;i++){
        int rkg=1,rks=1,rkb=1;
        for(int j=1;j<=n;j++)
            if(g[j]>g[i])
                rkg++;
        for(int j=1;j<=n;j++)
            if(s[j]>s[i])
                rks++;
        for(int j=1;j<=n;j++)
            if(b[j]>b[i])
                rkb++;
        printf("%d\n",min(min(rkg,rks),rkb));
    }
    return 0;
}

100 分做法

注意到小朋友们的排序方式其实只有三种，分别用三种方式给小朋友们排序，然后计算每个小朋友的排名即可。

计算排名时，如何处理并列的问题呢？

在 sort 结束后从前往后记录排名，对于第 i 个小朋友，如果他和上一个人奖牌数一样，那么他的排名等于上一个人的排名，否则排名等于 i。

假设有 5 个小朋友，排序后 5 个小朋友的奖牌数分别为 8,8,8,6,5，下面为计算排名的图示。

注意，计算每个小朋友的排名后，我们要对应到这个小朋友原来的编号，所以小朋友的结构体中，不仅要存金牌、银牌、铜牌数量，还要存小朋友原来的编号。

#include<bits/stdc++.h>
using namespace std;
struct child{int g,s,b,ind;}a[200005];
bool cmpg(child x,child y){return x.g>y.g;}
bool cmps(child x,child y){return x.s>y.s;}
bool cmpb(child x,child y){return x.b>y.b;}
int n,rk[200005];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&a[i].g,&a[i].s,&a[i].b);
        a[i].ind=i;
    }
    //处理金牌
    sort(a+1,a+n+1,cmpg);
    a[0]={-1,-1,-1,0};
    int crk=1;
    for(int i=1;i<=n;i++){
        if(a[i].g!=a[i-1].g)
            crk=i;
        rk[a[i].ind]=crk;//注意去更新 a[i].ind 这个小朋友而非 i
    }
    //处理银牌
    sort(a+1,a+n+1,cmps);
    a[0]={-1,-1,-1,0};
    crk=1;
    for(int i=1;i<=n;i++){
        if(a[i].s!=a[i-1].s)
            crk=i;
        rk[a[i].ind]=min(rk[a[i].ind],crk);
    }
    //处理铜牌
    sort(a+1,a+n+1,cmpb);
    a[0]={-1,-1,-1,0};
    crk=1;
    for(int i=1;i<=n;i++){
        if(a[i].b!=a[i-1].b)
            crk=i;
        rk[a[i].ind]=min(rk[a[i].ind],crk);
    }

    for(int i=1;i<=n;i++)
        printf("%d\n",rk[i]);
    return 0;
}