P8342 [COCI2021-2022#6] Med 题解
P8342 [COCI2021-2022#6] Med 题解
蒟蒻题解，不喜勿喷
题目传送门
step 1 题目理解
简单地说，这个题目就是一个排序的运用。
在最后一轮比赛开始前，输出每个养蜂人的最佳排名以及最差排名。
step 2 解题思路
要求出最佳排名和最差排名，就要首先了解对于一位养蜂人的最佳情况和最差情况分别是什么。
我们可以自行带入一下，如果我是一名养蜂人，在最后一场比赛开始前，最好的情况就是最后一场比赛我自己一个人得满分，其他人都零分，而最差情况自然就是我自己一人得零分，其他人都得满分。
根据这两种情况，我定义了两个数组，maxbi 以及 minbi，用来存放第i个养蜂人的最佳得分情况和最差得分情况（其实在做完此题后才发现，这样有点画蛇添足了，但是这样做更加容易理解 至少我觉得是的）。
然后就是排序阶段了，我这里使用的 c++ 函数库自带的 sort() 函数进行结构体类型变量的排序。
结构体变量由得分和养蜂人的编号组成。排序阶段，外层是一个 i 从 1 到 n 的大循环，表示我们要求的养蜂人的编号。在循环内部，分为两个部分，分别计算最佳排名和最差排名。最佳排名部分，将结构体的下标为 i 的元素的得分设为 maxbi 其余的元素都将得分设为 minbi ，最差部分 maxbi 和 minbi 恰好相反。在排序后，找到养蜂人编号为 i 的元素，直接输出该元素的下标即可。
这样，该题的核心部分就完成了
在排序时有几点需要注意：
1.结构体变量的组成
2.字典序的比较
3.比较时需要自定义cmp比较函数
结构体：
struct node{
int num;//得分情况
int id;//养蜂人编号
};字典序比较：
bool jdg(string a,string b){
int a_len=a.size(),b_len=b.size(),i=0,j=0;
while(a_len!=0&&b_len!=0){
if(a[i++]==b[j++]){a_len--;b_len--;continue;}
return a[i-1]<b[i-1];
//如果两字母相等，则继续比较，否则直接返回 a[i-1]<b[i-1] 的值
}
if(a_len==0) return 0;
return 1;
//如果其中a名字已完全比较完，则返回0，否则返回1
}cmp比较函数：
bool cmp(node a,node b){
if(a.num==b.num) return jdg(name[a.id],name[b.id]);
//若两得分相等，则比较名字的字典序
return a.num>b.num;
//若两得分不相等，则返回 a.num>b.num 的值
}step 3 AC代码
AC代码如下，悉数奉上
因为本人太蒻，这道题代码比较长，没有做相应的一些优化，各位通过该题的大佬勿喷
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
string name[N];
int maxbi[N],minbi[N],n,x;
//maxbi数组存放最大得分，minbi数组存放最小得分
struct node{//进行结构体排序的结构体
int num;//得分情况
int id;//养蜂人编号
};
bool jdg(string a,string b){//判断名字的字典序
int a_len=a.size(),b_len=b.size(),i=0,j=0;
while(a_len!=0&&b_len!=0){
if(a[i++]==b[j++]){a_len--;b_len--;continue;}
return a[i-1]<b[i-1];
}
if(a_len==0) return 0;
return 1;
}
bool cmp(node a,node b){//比较函数
if(a.num==b.num) return jdg(name[a.id],name[b.id]);
return a.num>b.num;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){//输入部分
cin>>name[i];
for(int j=1;j<=5;j++){
cin>>x;
minbi[i] += x;
}
maxbi[i] = minbi[i] + 500;
}
node nst[n+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){//排序前处理
if(j==i) nst[j].num=maxbi[j];
else nst[j].num=minbi[j];
nst[j].id = j;
}
sort(nst+1,nst+n+1,cmp);
for(int j=1;j<=n;j++) if(nst[j].id==i) cout<<j<<' ';
//以上为最佳情况计算和输出
for(int j=1;j<=n;j++){//排序前处理
if(j!=i) nst[j].num=maxbi[j];
else nst[j].num=minbi[j];
nst[j].id = j;
}
sort(nst+1,nst+n+1,cmp);
for(int j=1;j<=n;j++) if(nst[j].id==i) cout<<j<<endl;
//以上为最差情况计算和输出
}
return 0;
}