自动搬运

查看原文

来自洛谷，原作者为

	Ravener AFOed,AFChed|INTP-A|活！粉福启动！|> 最后在线时间：2024年10月11日21时23分 < 由 exOIso 发送激光

搬运于2025-08-24 21:16:15，当前版本为作者最后更新于2024-04-23 20:36:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先看到这道题，知道这是一个排序夹杂了结构体的题。
然而看到排序规则时彻底懵了：

1. 比较总分，高者靠前；
2. 如果总分相同，则比较语文和数学两科的总分，高者靠前；
3. 如果仍相同，则比较语文和数学两科的最高分，高者靠前；
4. 如果仍相同，则二人并列。

于是在经过了 114514 次思考后，有了下面的代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct student
{
	int chn=0;//语文
  	int mah=0;//数学
      	int eng=0;//英语
  	int sum=0;//总分
  	int num=0;//序号
	int pm=0;//排名
};
bool cmp1(student a,student b)
{
	if(a.sum!=b.sum)//对应规则 1
		return a.sum>b.sum;
	else if((a.mah+a.chn)!=(b.mah+b.chn))//对应规则 2
		return (a.mah+a.chn)>(b.mah+b.chn);
	else if(max(a.mah,a.chn)!=max(b.mah,b.chn))//对应规则 3
		return max(a.mah,a.chn)>max(b.mah,b.chn);
	else//对应……？（挖个坑，后文再填）
		return a.num<b.num;
}
main()
{
	student stu[200005];
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>stu[i].chn>>stu[i].mah>>stu[i].eng;
		stu[i].sum=stu[i].chn+stu[i].mah+stu[i].eng;
		stu[i].num=i;
	}
	sort(stu+1,stu+1+n,cmp1);
 	for(int i=1;i<=n;i++)
		stu[i].pm=i;
	for(int i=1;i<=n;i++)
		cout<<stu[i].pm<<"\n";
	return 0;
}

然而结局嘛……
不用说的，全 WA 了。

为何？
看了一下输出格式：

注意：请不要按排名输出同学的序号，而是按同学的顺序输出他们各自的排名。

原来如此。
又想了 1919810 次后，就有了下面的代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct student
{
	int chn=0,mah=0,eng=0,sum=0,num=0;
	int pm=0;
};
bool cmp1(student a,student b)
{
	if(a.sum!=b.sum)
		return a.sum>b.sum;
	else if((a.mah+a.chn)!=(b.mah+b.chn))
		return (a.mah+a.chn)>(b.mah+b.chn);
	else if(max(a.mah,a.chn)!=max(b.mah,b.chn))
		return max(a.mah,a.chn)>max(b.mah,b.chn);
	else
		return a.num<b.num;
}
bool cmp2(student a,student b)
{
	return a.num<b.num;
}
main()
{
	student stu[200005];
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>stu[i].chn>>stu[i].mah>>stu[i].eng;
		stu[i].sum=stu[i].chn+stu[i].mah+stu[i].eng;
		stu[i].num=i;
	}
	sort(stu+1,stu+1+n,cmp1);
  	for(int i=1;i<=n;i++)
		stu[i].pm=i;
	sort(stu+1,stu+1+n,cmp2);
	for(int i=1;i<=n;i++)
		cout<<stu[i].pm<<"\n";
	return 0;
}

这里多了的 bool cmp2(student a,student b) 和 sort(stu+1,stu+1+n,cmp2) 就是用来实现这一功能的。

然而……
还是全 WA 了。

又是为何？
仔细再读一遍题目：

你需要输出每位同学的排名，如遇 $x$ 人并列，则他们排名相同，并留空后面的 $(x-1)$ 个名次。

那么，具体怎么实现？
这是我想了 956382 次后想出来的做法：

首先，在结构体里多定义一个 bool 型变量，并赋值为 false：

struct student
{
	int chn=0,mah=0,eng=0,sum=0,num=0;
	int pm=0;
	bool iscp=0;
};

然后再把排序规则的最后一个 else 改一改：

else//填前面的坑，做标记，对应规则 4
{
	if(a.num<b.num)
		b.iscp=1;
	else
		a.iscp=1;
	return a.num<b.num;
}

接着在两个 sort 语句间的 for 循环改一改：

for(int i=1;i<=n;i++)//查重
{
	if(stu[i].pm) continue;//关键，做到留空名次
	else
	{
		stu[i].pm=i;
		int cur=1;
		while(stu[i+cur].iscp)//关键，做到排名相同
		{
			stu[i+cur].pm=stu[i].pm;
			cur++;
		}
	}
}

这样便大功告成了！

最后，把这些整合一下，AC 代码就有了！
代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct student
{
	int chn=0,mah=0,eng=0,sum=0,num=0;
	int pm=0;
	bool iscp=0;
};
bool cmp1(student a,student b)
{
	if(a.sum!=b.sum)
		return a.sum>b.sum;
	else if((a.mah+a.chn)!=(b.mah+b.chn))
		return (a.mah+a.chn)>(b.mah+b.chn);
	else if(max(a.mah,a.chn)!=max(b.mah,b.chn))
		return max(a.mah,a.chn)>max(b.mah,b.chn);
	else
	{
		if(a.num<b.num)
			b.iscp=1;
		else
			a.iscp=1;
		return a.num<b.num;
	}
}
bool cmp2(student a,student b)
{
	return a.num<b.num;
}
main()
{
	student stu[200005];
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>stu[i].chn>>stu[i].mah>>stu[i].eng;
		stu[i].sum=stu[i].chn+stu[i].mah+stu[i].eng;
		stu[i].num=i;
	}
	sort(stu+1,stu+1+n,cmp1);
	for(int i=1;i<=n;i++)
	{
		if(stu[i].pm) continue;
		else
		{
			stu[i].pm=i;
			int cur=1;
			while(stu[i+cur].iscp)
			{
				stu[i+cur].pm=stu[i].pm;
				cur++;
			}
		}
	}
	sort(stu+1,stu+1+n,cmp2);
	for(int i=1;i<=n;i++)
		cout<<stu[i].pm<<"\n";
	return 0;
}

（题解仅供参考，如有谬误或纰漏欢迎 at 我并指正）