数组拆分排序：求转为非降序的最少操作次数及结果数组

问题定义 #

给定一个整数数组，允许执行以下操作：将数组中的任意元素替换为两个和等于该元素的元素。例如，数组{4, 11, 7}可将array[1]替换为5和6，得到数组{4, 5, 6, 7}。需要返回两个结果：

• 将整个数组转为非降序的最少操作次数
• 最终排序后的数组

示例说明 #

对于数组{3,9,3}，最优解法是将9拆分为3,3,3，此时数组变为{3,3,3,3}，操作次数为2（每次拆分1个元素为2个，拆两次得到3个元素）。

个人思路尝试 #

目前尚未推导通用解法，初步思路如下：

• 若当前需要拆分的元素，其半值向上取整大于右侧相邻元素，则重复用该元素减去右侧元素，拆分出多个等于右侧元素的值，直到剩余值不大于右侧元素
• 若半值向上取整不大于右侧元素，则将元素拆分为半值向上取整和剩余值（例如7拆为4和3），后续再根据情况处理拆分后的元素

内容的提问来源于stack exchange，提问作者programcggg