题解P5754 【排名】

· · 题解

这两个小题的解法不相同！

我们先看第一小题。

每个人都最多只有一个已知的比他成绩好的，我们可以把比他成绩好的人看做他的父节点，这样，我们就得到了一棵树。而这棵树的根节点是 0。

看样例，要使编号小的排在前面，我们一开始先考虑 1（不惜一切代价将未放入的编号最小的放入）， 1 的祖先有 3,2 。要放入 1，就必须先放入 2,3 （他的所有祖先）。所以，现在的排名是：

NO.1 2 号

NO.2 3 号

NO.3 1 号

1,2,3 号都已排名，还剩一个 4，4 的祖先 2 已经在队伍中，所以他可以直接进入，最终排名 2 3 1 4。按照题目的排列方式（第 i 个数输出 i 的名次）答案是 3 1 2 4 。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5*2+10;
int ans[N],a[N],cur=0;
//ans[i]指第i名的名次，a[i]是第i人的祖先，cur代表队伍中的人数。
int pm(int x)
{
    if(ans[x]!=-1)//x以及x的祖先已经入队了
        return cur;
    else
        return ans[x]=pm(a[x])+1;//递推，x是他的祖先的下一个
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<=n;i++)
        ans[i]=-1;
    ans[0]=0;
    //初始化
    for(int i=1;i<=n;i++)
    {
        if(ans[i]==-1)//如果他还没有进队
        {
           ans[i]=pm(i);//让他进队
           cur=ans[i];//现在有ans[i]个人在队伍中
        }
    }
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    printf("\n");
    return 0;
}

第二小题

如题目所述，让编号前的同学靠后不等于编号后的同学靠前。（例如 4 0 0 0 1 应该得出的是 3 2 4 1 而不是 1 4 3 2 ） 我们在第一题时是从多点到根点，而这一题我们需要从根点到多点，类似于 bfs 和拓扑。

还是样例。与 0 联通的只有 2，所以我们只能请 2 入队。 2 入队后，他的儿子便可以入队了。他的儿子有 3,4 两位，但我们要让编号小的后入队，所以 4 先入队，接着是 3。3 的儿子——1 也解禁并入队，最终排名 2 4 3 1，答案是 4 1 3 2。

转化为代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5*2+10;
priority_queue<int> q;//优先队列，编号大的在前
int cnt[N],a[N],cur=0;
vector<int>g[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        g[a[i]].push_back(i);
    }
    //标注出每个人的所有儿子
    for(int i=0;i<=n;i++)
        cnt[i]=-1;
    //初始化
    q.push(0);
    //与0点联通的点（没有父节点）可以进队
    while(q.size())
    {
        int u=q.top();
        q.pop();
        cnt[u]=cur;
        cur++;
        //在队伍中编号最大的出队并获取排名
        for(int i=0;i<g[u].size();i++)
            q.push(g[u][i]);
        //u的儿子也可以获取排名了
    }
    for(int i=1;i<=n;i++)
        printf("%d ",cnt[i]);
    return 0;
}