集合

 

【问题描述】

给定一个可重集合，一开始只有一个元素0。然后你可以操作若干轮，每一轮，你需要对于集合中的每个元素𝑥进行如下三种操作之一：

1、将𝑥变为𝑥 + 1。

2 、将𝑥分裂为两个非负整数𝑦, 𝑧，且满足𝑥 = 𝑦 + 𝑧。

3 、什么都不做。

每一轮，集合中的每个元素都必须进行上面三个操作之一。对于一个最终的集合，你的任务是判断至少进行了多少轮。

【输入文件】

第一行为一个正整数𝑛，表示集合的最终大小。第二行为𝑛个非负整数，描述集合中的元素。

【输出文件】

输出一个非负整数，为最少的轮数。

【输入输出样例】

multiset.in	multiset.out
5 0 0 0 3 3	5

【数据规模和约定】

设集合中最大的元素为𝑚。

对于10%的数据，满足𝑛, 𝑚 ≤ 10。对于30%的数据，满足𝑛, 𝑚 ≤ 100。

对于50%的数据，满足𝑛 ≤ 1000，𝑚 ≤ 10000。对于100%的数据，满足1 ≤ 𝑛, 𝑚 ≤ 1000000。

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 int n,maxx,a[1000010],c[5000010],ans;
 5 int main()
 6 {
 7     scanf("%d",&n);
 8     for(int i=1;i<=n;++i)
 9     {
10         scanf("%d",&a[i]);
11         maxx=max(maxx,a[i]);
12         c[a[i]]++;
13     }
14     for(int i=1;i<=maxx;++i)
15     {
16         ans++;
17         c[0]=c[i]+(c[0]+1)/2;
18     }
19     for(;c[0]>1;c[0]=(c[0]+1)/2)
20     ans++;
21     printf("%d\n",ans);
22     return 0;
23 }