解题思路
一次优化操作选择的是当前所有正数货物中某一个连续段,并让这一段全部减少 1。可以把数组看成柱状图:在某个高度层 h 上,所有 goodProceeTime[i] >= h 的位置会形成若干个连续段,每个连续段长度就是在这一层执行一次优化能减少的总处理时间。
因此,问题转化为:统计所有高度层上的正连续段长度,从中选择最多 optimize 个最大的长度,使总减少量最大,最终答案为原始总和减去最大减少量。
为了高效统计这些长度,按处理时间从高到低激活位置,并用并查集维护当前高度层的连续段。每个连通段在若干个连续高度层中保持不变,记录它的起始高度;当它因为更低高度的新位置加入而合并时,先结算旧连续段贡献了多少次对应长度。最后得到 countByLen[len],表示长度为 len 的优化收益出现了多少次。再从大到小取前 optimize 个收益即可。
复杂度分析