← 返回题目列表

AtCoder · utpc2013_04

D. 破碎的堆

中文机器翻译题面 查看原题

問題

背景

鳗鱼王国的公主热爱数据结构。所以国王准备在她生日送她许多“代表二进制堆的数组”。

“表示二元堆的数组”指的是 i 元素的值为2i+1如果某个元素存在,则该元素严格小于它,同样,如果第2i+2个元素存在,则它严格小于它,这个条件在所有元素中都满足的数组被称为二叉堆。比如 [0,1,4,2,3] 是表示二叉堆的数组。因为第0个元素0比第1个元素和第2个元素1和 按字典顺序比较4更小,比第1个元素1比第3个元素和第4个元素的2和 按字典顺序比较3也更小……这样的条件全部成立。这样的数组可以被看作是一种树结构,其中第i个元素的子节点是第2i+1个元素和第2i+2个元素,并且具有父节点的值始终较小的特征。公主沉迷于利用这一特征来提高排序等各种算法的效率。

「バイナリヒープを表現した配列」の例
図 1:“表示二叉堆的数组”的例子

然而,不幸的是,国王把好不容易做好的“表示二叉堆的数组”掉落并弄坏了!现在国王手里只剩下了“表示二叉堆的数组”的后半部分。必须尽快恢复原来的“表示二叉堆的数组”。国王记得,原数组的元素都是非负整数,并且没有重复值。希望你能利用这些信息来恢复数组。

課題

换句话说,对于输入 A0 ... AN-1 , H0 ... HM-1 要求找到满足以下条件的数组 M 并将其长度作为答案输出。

  • Hi 就是全部 0 的整数
  • 数组的所有元素都是互不相同的。也就是说,i \neq j 如果 Hi \neq Hj
  • 它是表示二叉堆的数组。也就是说,它始终 Hi \lt H2i+1 和 Hi \lt H2i+2
  • A 是 在 H 是其后缀。也就是说,对于所有 0 \leq k \lt N , 定义Ak = HM-N+k

存在多种可能的情况时,取最小的。 M 。满足条件的 H 不存在,则 -1 回答。

配点

100

入力

输入按以下格式给出。

N
A0 A1 ... AN-1

制約

输入中的每个变量都满足以下约束。

  • 1 \leq N \leq 100
  • 0 \leq Ai \leq 109
  • Ai 是彼此不同的非负整数

出力

问题的解决办法 在1行输出。 没有

入力例1

3
4 2 3

输入示例 1 的输出示例 路径

5

[4,2,3] 是4(第0个,比2呀 请注意,它可能是3(第1,第2个元素要大,因此不满足条件。[*,4,2,3] 形式的数组也因为大于4(第1个,比3(第3 = 2 \times 1+1个元素,所以无论*填入什么值都不满足条件。它是以[0,1,4,2,3] 是, 当[4,2,3] 作为后缀表示二叉堆的最短数组。注意,

入力例2

3
3 1 2

输入示例 2 的输出示例

-1

[0,1,3,1,2] 呀 请注意,它可能是 [-1,0,3,1,2] 由于数组元素没有重复且为非负整数等原因,不满足条件。

入力例3

4
10 20 40 30

输入示例 3 的输出示例

4

入力例4

4
9 2 3 6

输入示例 4 的输出示例

8