专栏文章

题解

小小陈同学cyh
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqri39r
此快照首次捕获于
2025/12/04 09:33
3 个月前
此快照最后确认于
2025/12/04 09:33
3 个月前
查看原文

题意：

第一行输入两个数 nn ， mm 表示有 nn 个数， mm 对不等关系，接下来 mm 行，每行两个数 ii ， jj 表示 a[i]>a[j]a[i]>a[j]
问最少还需要比较多少次才能确定一个数是第二大的数
数据范围： n,m≤106n,m\le10^6 1000ms1000ms 512MB512MB

思考：

什么数可能是第二大的数不太好找，那就考虑正难则反，求什么数不能成为第二大的数，剩下的自然是可能成为第二大的
显然的：当 a[i]>a[j]a[i]>a[j] 并且存在 a[k]>a[j]a[k]>a[j] 时， a[j]a[j] 显然不会是第二大的数，当然 a[k]>a[j]a[k]>a[j] 不一定是题目直接给出的条件，可以是推理出来的，比如有 a[k]>a[i]a[k]>a[i] 也可以证明 a[j]a[j] 不是第二大的数
考虑时间复杂度，排除 n2n^2 和 nmnm ，看上去只有 nlogn（nlogm）n log n（n log m） 和线性可以通过，明显线段树，二分答案一点用都没有，建图也不是一棵树，跑最短路也没什么用

等等，图？

输入 i，ji，j 就连一条从 ii 到 jj 的有向边，用链式前向星存边，并且将 bz[j]++bz[j]++ ， bz[i]bz[i] 的值表明至少有几个数比 a[i]a[i] 大
套路的，我们可以用 visvis 表示一个点有没有操作过，从 11 到 nn 遍历，若 bz[i]>0bz[i]>0 ，证明至少有一个数比 a[i]a[i] 大，那么对于每一个 a[i]>a[j]a[i]>a[j] 都有 a[k]>a[j]a[k]>a[j] 那么就可以把所有这样的 bz[j]bz[j] 赋为 22 ，并立刻操作 jj
这样就能保证不重不漏地把每一个不可能成为第二大的数筛掉，这很好证明，读者可以自己尝试一下
无视掉已经被排除的点，得到这样一张图：
可以发现是很多棵一层树，也就是每个 bz[i]=0bz[i]=0 连接了若干个 bz[j]=1bz[j]=1
考虑只有一棵树，那么显然次数是 bz[j]=1bz[j]=1 的个数减 11
不难想到，每次比较子节点最小的两棵子树一定不劣（可以用调整法证明），那么就 ans++ans++ （已经做了一次比较了），然后把最小的两个树出队，然后入队比较大的那个数加 11

AC代码

CPP
#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)O(nlogn) 常数极小，实测只需要200ms不到
当然可以用合并果子的思想优化到 O(n+m)O(n+m)，不过本人比较懒就用 STLSTL 了

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...