题解

· · 个人记录

题意：

第一行输入两个数 n ， m 表示有 n 个数， m 对不等关系，接下来 m 行，每行两个数 i ， j 表示 a[i]>a[j]

问最少还需要比较多少次才能确定一个数是第二大的数

数据范围： n,m\le10^6 1000ms 512MB

思考：

什么数可能是第二大的数不太好找，那就考虑正难则反，求什么数不能成为第二大的数，剩下的自然是可能成为第二大的

显然的：当 a[i]>a[j] 并且存在 a[k]>a[j] 时， a[j] 显然不会是第二大的数，当然 a[k]>a[j] 不一定是题目直接给出的条件，可以是推理出来的，比如有 a[k]>a[i] 也可以证明 a[j] 不是第二大的数

考虑时间复杂度，排除 n^2 和 nm ，看上去只有 n log n（n log m） 和线性可以通过，明显线段树，二分答案一点用都没有，建图也不是一棵树，跑最短路也没什么用

等等，图？

输入 i，j 就连一条从 i 到 j 的有向边，用链式前向星存边，并且将 bz[j]++ ， bz[i] 的值表明至少有几个数比 a[i] 大

套路的，我们可以用 vis 表示一个点有没有操作过，从 1 到 n 遍历，若 bz[i]>0 ，证明至少有一个数比 a[i] 大，那么对于每一个 a[i]>a[j] 都有 a[k]>a[j] 那么就可以把所有这样的 bz[j] 赋为 2 ，并立刻操作 j

这样就能保证不重不漏地把每一个不可能成为第二大的数筛掉，这很好证明，读者可以自己尝试一下

无视掉已经被排除的点，得到这样一张图：

可以发现是很多棵一层树，也就是每个 bz[i]=0 连接了若干个 bz[j]=1

考虑只有一棵树，那么显然次数是 bz[j]=1 的个数减 1

不难想到，每次比较子节点最小的两棵子树一定不劣（可以用调整法证明），那么就 ans++ （已经做了一次比较了），然后把最小的两个树出队，然后入队比较大的那个数加 1

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,head[1000005],fa[1000005],bz[1000005],a[1000005],ans;
bool vis[1000005];
struct edge{
    int to,nextt;
}edge[1000005];
priority_queue<int,vector<int>,greater<int>> q;
int in(){int k=0,f=1;char c=getchar();while (c<'0'||c>'9'){if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9'){k=k*10+c-'0';c=getchar();}return k*f;}
void addedge()
{
    int x=in(),y=in();
    fa[y]=x;
    bz[y]++;
    cnt++;
    edge[cnt].to=y;
    edge[cnt].nextt=head[x];
    head[x]=cnt;
}
void solve(int z)
{
    vis[z]=true;
    for (int i=head[z];i;i=edge[i].nextt)
    {
        bz[edge[i].to]=2;
        if (!vis[edge[i].to])
        {
            solve(edge[i].to);
        }
    }
}
signed main()
{
    n=in();m=in();
    for (int i=1;i<=m;i++)
    {
        addedge();
    }
    for (int i=1;i<=n;i++)
    {
        if (!vis[i]&&bz[i]>0)
        {
            solve(i);
        }
    }
    for (int i=1;i<=n;i++)
    {
        if (bz[i]==1)
        {
            a[fa[i]]++;
        }
    }
    for (int i=1;i<=n;i++)
    {
        if (!bz[i])
        {
            ans++;
            q.push(a[i]);
        }
    }
    while (q.size()>1)
    {
        q.pop();
        q.push(q.top()+1);
        q.pop();
    }
    cout<<q.top()-1+ans-1;
    return 0;
}

时间复杂度 O(nlogn) 常数极小，实测只需要200ms不到

当然可以用合并果子的思想优化到 O(n+m)，不过本人比较懒就用 STL 了