字节笔试10-8 合并

题目描述：
小红拿到一个数组，他可以进行合并的操作：两个相同的数x，合并之后从数组中删除，并添加一个2x。仅允许一次，可以添加任意一个值。
问最多能合并几次？

输入为，第一行：数组长度n，第二行：n个元素
输出为，你添加了什么数字，最多合并几次 (有多个答案的情况任意一种即可)

样例：
input
3
1 1 3

output
3 2

这个题目有一点难度，因为他的n最多是有10^5的，最多允许nlogn时间复杂度。我和朋友讨论后认为可以这么做：

①预处理：首先将数组中已有的相同元素合并，得到一个不重复的数组，合并次数为res1 ②统计最长的等比数列有多长，长为res2 ③答案等于res1+res2，至于添加了什么数字，就是等比数列的最小值。

解释一下为什么这么想：因为能合并肯定先合并，后面再考虑能不能加数字，能加的话什么才是最优解？那当然是能够造成多米诺骨牌效应的，也就是能够1合2,2合4这样一直推下去的，所以是一个等比数列，数列有多长就合并多少次，如果没有这样的等比数列，那我随便找个数合并也能多出1次。

代码如下：

from collections import Counter
#合并
n = int(input().strip())
arr = list(map(int,input().strip().split()))

#预处理
res = 0
cnt = Counter(arr)
while 1: #当存在重复元素时，继续循环
    cnt_new = Counter()
    for key in cnt:
        # print(cnt_new,cnt,key)
        if cnt[key]%2==1:
                cnt_new[key] = 1
        if cnt[key]>=2:
            cnt_new[2*key] = cnt[key]//2
            res+=cnt_new[2*key]   
    #新老相等，跳出
    if cnt==cnt_new:break
    cnt = cnt_new
    
# print(cnt,res)

#算最长链长
keys = list(cnt.keys())
keys.sort()
vis = set()
max_chain_len = 1
head = keys[0]
for key in keys:
    tmp = 0
    cur = key
    while cur in cnt and cur not in vis:
        vis.add(cur)
        cur*=2
        tmp+=1
    if tmp>max_chain_len:
        max_chain_len = tmp
        head = key
res+=max_chain_len
print(head,res)