自动搬运

查看原文

来自洛谷，原作者为

	yummy 这个人是时代的眼泪，什么也没有留下

搬运于2025-08-24 23:05:02，当前版本为作者最后更新于2024-10-16 11:29:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

• 【3】sort 函数
• 【3】结构体

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;
}