#P18955. [Mladen Manev 2022 AT5] compression / 二叉树压缩

[Mladen Manev 2022 AT5] compression / 二叉树压缩

二叉树压缩

一棵有根有序满二叉树的每个内部结点都有两个孩子,根的深度为 00。给定从左至右排列的全部 NN 个叶子的深度。保证输入描述一棵这样的树。

允许将树变成任意一棵叶子深度多重集合相同的有根有序满二叉树,之后进行压缩:如果一个结点的整棵子树中,所有叶子的最大深度与最小深度相差不超过 11,就可以把这棵子树替换为一个结点。可压缩若干互不相交的子树。

求最终结点数的最小值,并给出一棵能达到该最小值的树的从左至右叶子深度序列。

输入格式

第一行 NN。第二行按从左至右顺序给出原树的 NN 个叶子深度。

输出格式

第一行一个整数,表示压缩后的最少结点数。

第二行给出 NN 个整数,表示压缩前所选新树的叶子深度序列。它必须描述一棵有根有序满二叉树,与输入的叶子深度多重集合相同,并且确实能压缩到所报的最优结点数。

数据范围

1≤N≤5000001\le N\le500000。所有深度均为非负整数,且输入合法,因此叶子深度不超过 N−1N-1。

样例

8
3 3 3 3 2 4 4 3
3
2 3 3 3 3 3 4 4

原比赛只给出最优数而没有合法最优构造时可获部分分;本题包的 100 分配置要求最优数和构造均正确。

本题原为波兰 IOI 2020 选拔赛第二天 Kompresja drzew binarnych,由本网站 2022 年训练赛选用。官方分析。

来源与数据说明

2022 年 Dr. Mladen Manev,AT5,原题名 compression。赛事资料,原文题面见附件 statement.pdf。

原官方测试数据未能获取,本题使用依据原题规格编写的自建测试数据,并非官方原始数据。总分为 100 分。