主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 D: W老师的玩具

问题 D: W老师的玩具

时间限制: 2 Sec  内存限制: 128 MB
提交: 112  解决: 24
[提交][状态][讨论版]

题目描述

由于不小心让W老师在某道题上卡了十几发,A给W老师买了个玩具以表示歉意.

这个玩具可以看做一个多重集
最初,集合中只有一个元素0
每一轮,W老师会操作其中的每一个元素(设当前操作的为x)执行以下三种操作之一:
   
    1.  x=x+1
    2.  x分裂成两个非负整数a,b 即x=a+b,且a>=0,b>=0    
    3.  什么也不做

W老师玩了很久之后,已经不记得自己玩了多少轮了.

他很好奇自己最少玩多少轮才能把集合从开始变成现在的状态.

于是他把这个任务交给了A,如果A能找到答案他就会选择原谅他.但是A实在是太菜了,你能帮帮A吗?

输入

第一行,一个整数N,表示最终集合的大小

第二行为N个非负整数,表示最终集合的每一个元素

输出

一行,W老师最少玩的轮数

样例输入

4
1 1 1 1

样例输出

3

提示

单组数据

N<=1,000,000

0<=集合里的数字<=1,000,000


样例解释

第一轮:

0分裂成0 0

第二轮

0 0中每个0分裂成两个0,得到0 0 0 0

第三轮

每个0+1,得到1 1 1 1

[提交][状态][讨论版]