集合

 

【问题描述】

给定一个可重集合，一开始只有一个元素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。

采用贪心的思想，从最终的数列倒着往0推，为了更快地得到0，我们每次需要将非0的数进行-1操作，对于已经为0的两个数进行合并（与题目中的操作桥好像反），如果0的个数为奇数个，那么最后一个0不进行操作。

具体代码实现，我们如果将这些数每次都扫一遍，肯定会炸，因为很大一部分数是进行-1操作，所以我们与其将他们-1，不如将标准+1，也就是每次将一个递加的i看做0，那么只需要考虑0的个数就好了，并且将i的个数加到0的个数中去，将上一次0的个数除以2取上整（今天学到一种取上整的小技巧，（i+1）/2）。

所以我们用一个c【i】存i的个数，顺便记录最大的i，然后先用一个循环进行max（i）次操作，再用一个循环将未合并的0合并。两个循环都用ans来记录进行的次数，最后ans即为答案。

附上代码

 

 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 }