P8342题解

· · 题解

传送门

题目大意
有 n 个人进行 6 轮比赛，已经知道前 5 轮的得分，每个人第 6 轮的可能得分在 0 分到 500 分之间。最终排名按照第一关键字总分从大到小排序，如果第一关键字总分相同按照第二关键字名字的字典序从小到大排序，保证每个人名字不同。询问每个人在最终排名中可能的最佳和最差位置。

解题思路
显然如果一个人想拿到最佳名次，那么最后一轮只有这个人得到了 500 分其他人都得到 0 分（什么逆天改命）。如果一个人拿到了最差名次，我们可以让这个人最后一轮得到 0 分其他人都得到 500 分（老天：我又改回来了），相当于其他人都得到 0 分而这个人得到了 -500 分。这样我们就可以参照P7910 [CSP-J 2021] 插入排序的做法，首先对所有人前 5 轮的状态进行排序，考虑第 6 轮得分相当于对单点进行修改，利用插入排序的思想 O(n) 去维护最终排名。时间复杂度为 O(n^2)。

代码如下

#include<bits/stdc++.h>
using namespace std;
long long read(){
    long long x=0,sgn=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')sgn=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
    return x*sgn;
}
long long n,x,a[510],pos[510],val[510];
string st[510];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>st[i];
        for(int j=1;j<=5;j++){
            cin>>x;
            val[i]+=x;
        }
        pos[i]=i;//pos[i]表示第 i 个人当前的排名
        a[i]=i;//a[i]表示当前排名第 i 个人是输入数据中的第几个人
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n-i;j++)
            if(val[a[j]]<val[a[j+1]] || val[a[j]]==val[a[j+1]] && st[a[j]]>st[a[j+1]]){
                swap(a[j],a[j+1]);
                swap(pos[a[j]],pos[a[j+1]]);
            }//O(n^2)冒泡排序处理初始排名
    for(int i=1;i<=n;i++){
        val[i]+=500;//最好名次：自己拿了500分，其他人都是0分 
        for(int j=pos[i]-1;j>=1;j--)
            if(val[a[j]]<val[a[j+1]] || val[a[j]]==val[a[j+1]] && st[a[j]]>st[a[j+1]]){
                swap(a[j],a[j+1]);
                swap(pos[a[j]],pos[a[j+1]]);
            }
            else break;
        cout<<pos[i]<<" ";
        val[i]-=500;//消除影响回到最初状态
        val[i]-=500;//最坏名次：其他人都是0分，自己拿了-500分 
        for(int j=pos[i]+1;j<=n;j++)
            if(val[a[j]]>val[a[j-1]] || val[a[j]]==val[a[j-1]] && st[a[j]]<st[a[j-1]]){
                swap(a[j],a[j-1]);
                swap(pos[a[j]],pos[a[j-1]]);
            } 
            else break;
        cout<<pos[i]<<endl;
        val[i]+=500;//消除影响回到最初状态
        for(int j=pos[i]-1;j>=1;j--)
            if(val[a[j]]<val[a[j+1]] || val[a[j]]==val[a[j+1]] && st[a[j]]>st[a[j+1]]){
                swap(a[j],a[j+1]);
                swap(pos[a[j]],pos[a[j+1]]);
            }
            else break;
    }
    return 0;
}