P11242 题解

· · 题解

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;
}