一次优化操作选择的是当前所有正数货物中某一个连续段,并让这一段全部减少 1。可以把数组看成柱状图:在某个高度层 h 上,所有 goodProceeTime[i] >= h 的位置会形成若干个连续段,每个连续段长度就是在这一层执行一次优化能减少的总处理时间。
因此,问题转化为:统计所有高度层上的正连续段长度,从中选择最多 optimize 个最大的长度,使总减少量最大,最终答案为原始总和减去最大减少量。
为了高效统计这些长度,按处理时间从高到低激活位置,并用并查集维护当前高度层的连续段。每个连通段在若干个连续高度层中保持不变,记录它的起始高度;当它因为更低高度的新位置加入而合并时,先结算旧连续段贡献了多少次对应长度。最后得到 countByLen[len],表示长度为 len 的优化收益出现了多少次。再从大到小取前 optimize 个收益即可。
某物流仓库有一个长度为 n 的货物处理队列,队列中的每个元素代表一个货物单元所需的处理时间(单位:分钟)。
管理员可以使用一种特殊的“处理优化”机制:每次优化操作可以选择一组连续的货物单元(注意:如果某个货物单元的处理时间为 0,则它两边的货物单元不视为连续),并将选中组内每个货物单元的处理时间减少 1 分钟。
给定一个货物处理队列 nums(表示各货物单元的处理时间)和一个整数 k(表示最多可进行的优化操作次数),你需要计算在不超过 k 次操作的情况下,仓库处理完所有货物的最短总处理时间。
连续性的定义:
只有处理时间大于 0 的相邻货物单元才被视为连续。 如果遇到处理时间为 0 的货物单元,它会打断连续性。例如: 数组 [5,4,0,3] 被 0 分割为两个连续段:[5,4] 和 [3]。
操作规则: 每次操作只能选择一个连续段,并将段内所有货物单元的处理时间减 1。
操作后若某个货物单元的处理时间变为0,它可能会将原来的连续段分割为更小的段。
目标: 通过最多 k 次操作,使得最终所有货物单元的处理时间之和最小。
1 <= nums.length <= 105 0 <= nums[i] <= 105 0 <= k <= 105
输入
[5,4,0,3],1
输出
10
说明
操作选择: 由于 0 的存在,连续段为 [5,4] 和 [3]。选择较长的段 [5,4] 进行优化(减 1),得到 [4,3,0,3]。
总时间:4+3+0+3=10
返回值:10
输入
[5,3,4],3
输出
3
说明
操作过程:
第一次操作:全段 [5,3,4] → [4,2,3]
第二次操作:全段 [4,2,3] → [3,1,2]
第三次操作:全段 [3,1,2] → [2,0,1]
总时间:2+0+1=3
返回值:3