自动搬运

查看原文

来自洛谷，原作者为

	Aventurine_stone （已AFO）愿人生的赌局，赢的总是我们。

搬运于2025-08-24 23:05:37，当前版本为作者最后更新于2024-11-05 19:00:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

1. 题目分析

这道题题面有树，但其实就是一个简单的结论题，样例解释都把结论喂你嘴里了，注意一下输入的是叶子节点即可。

2. 题目做法

题目要我们包含的节点数最少，又因为输入的是叶子节点，所以我们构造的树必须有一个主干，也就是一条没有叶子节点的链，所有的输入的数都连接在主干上。
我们用主来表示主干上的节点，输来表示输入的节点，构造的树也就是下面这张图。

由于节点深度小于 $10^5$，我们可以用一个数组 $cnt$ 记录当前深度我们要放多少个叶子节点，并同时记录，深度最大的叶子节点深度为 $mx$，接下来只用从 $1$ 到 $mx$ 依次遍历 $cnt$ 数组即可，答案每次加 $cnt_i + 1$。由于这样算会使主干的结尾多一个点，所以最后让答案减一即可。

3. 代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100010;
inline int read()
{
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')
		c=getchar();
	while(c>='0'&&c<='9')
		x=(x<<1)+(x<<3)+c-'0',c=getchar();
	return x;
}
int n;
int a,mx,cnt[N],s;
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
		a=read(),cnt[a]++,mx=max(mx,a);
	for(int i=1;i<=mx;i++)
		s+=cnt[i]+1;
	printf("%d",s-1);
	return 0;
}