用什么程序做网站,网站开发什么叫前端后端,成免费crm破解版,山东免费网站制作【LetMeFly】3013.将数组分成最小总代价的子数组 II#xff1a;两个堆维护k-1小 滑动窗口
力扣题目链接#xff1a;https://leetcode.cn/problems/divide-an-array-into-subarrays-with-minimum-cost-ii/
给你一个下标从 0 开始长度为 n 的整数数组 nums 和两个 正 整数 k…【LetMeFly】3013.将数组分成最小总代价的子数组 II两个堆维护k-1小 滑动窗口力扣题目链接https://leetcode.cn/problems/divide-an-array-into-subarrays-with-minimum-cost-ii/给你一个下标从0开始长度为n的整数数组nums和两个正整数k和dist。一个数组的代价是数组中的第一个元素。比方说[1,2,3]的代价为1[3,4,1]的代价为3。你需要将nums分割成k个连续且互不相交的子数组满足第二个子数组与第k个子数组中第一个元素的下标距离不超过dist。换句话说如果你将nums分割成子数组nums[0..(i1- 1)], nums[i1..(i2- 1)], ..., nums[ik-1..(n - 1)]那么它需要满足ik-1- i1 dist。请你返回这些子数组的最小总代价。示例 1输入nums [1,3,2,6,4,2], k 3, dist 3输出5解释将数组分割成 3 个子数组的最优方案是[1,3] [2,6,4] 和 [2] 。这是一个合法分割因为 ik-1- i1等于 5 - 2 3 等于 dist 。总代价为 nums[0] nums[2] nums[5] 也就是 1 2 2 5 。 5 是分割成 3 个子数组的最小总代价。示例 2输入nums [10,1,2,2,2,1], k 4, dist 3输出15解释将数组分割成 4 个子数组的最优方案是[10] [1] [2] 和 [2,2,1] 。这是一个合法分割因为 ik-1- i1等于 3 - 1 2 小于 dist 。总代价为 nums[0] nums[1] nums[2] nums[3] 也就是 10 1 2 2 15 。 分割 [10] [1] [2,2,2] 和 [1] 不是一个合法分割因为 ik-1和 i1的差为 5 - 1 4 大于 dist 。 15 是分割成 4 个子数组的最小总代价。示例 3输入nums [10,8,18,9], k 3, dist 1输出36解释将数组分割成 4 个子数组的最优方案是[10] [8] 和 [18,9] 。这是一个合法分割因为 ik-1- i1等于 2 - 1 1 等于 dist 。总代价为 nums[0] nums[1] nums[2] 也就是 10 8 18 36 。 分割 [10] [8,18] 和 [9] 不是一个合法分割因为 ik-1和 i1的差为 3 - 1 2 大于 dist 。 36 是分割成 3 个子数组的最小总代价。提示3 n 1051 nums[i] 1093 k nk - 2 dist n - 2解题方法有序集合 滑动窗口n u m s numsnums第一个元素必选剩下k − 1 k-1k−1个元素的起始位置间隔必须≤ d i s t \leq dist≤dist。使用一个大小为d i s t 1 dist1dist1的滑动窗口每次求这个窗口中k − 1 k-1k−1小元素的和。问题变成了滑动窗口向右滑动过程中窗口中不断新增一个元素、移除一个元素的状态下如何保持计算k − 1 k-1k−1小的元素有哪些我们可以使用两个有序集合一个叫s t a g e stagestage代表(正在舞台上的)k − 1 k-1k−1小元素一个叫c a n d i d a t e candidatecandidate代表在窗口中但(暂)未被选中的元素。窗口右移过程中假设要新加入窗口的元素是i n inin移除窗口的元素是o u t outout对于o u t outout有如果o u t outout在c a n d i d a t e candidatecandidate候选集合中那么o u t outout永无上台之日直接移出候选如果o u t outout在s t a g e stagestage选中集合中那么o u t outout是时候退役了移出s t a g e stagestage集合并更新集合中元素之和对于i n inin有如果i n inin比s t a g e stagestage中最大元素小说明更优秀的人来了移出s t a g e stagestage集合中最大的那个将i n inin加入s t a g e stagestage集合并更新s t a g e stagestage集合中元素之和否则将i n inin加入候选之后进行s t a g e stagestage集合大小的调整如果s t a g e stagestage集合小于k − 1 k-1k−1说明有人退役暂无人顶上从c a n d i d a t e candidatecandidate中选最小的那个顶上(移出c a n d i d a t e candidatecandidate并加入s t a g e stagestage)并更新s t a g e stagestage集合中元素之和如果s t a g e stagestage集合大于k 1 k1k1说明有更优秀的人来了要把s t a g e stagestage中最大的那个移出并加入到c a n d i d a t e candidatecandidate并更新s t a g e stagestage集合中元素之和整个滑动窗口移动的过程中所有s t a g e stagestage元素和中最小的那个即为答案。为了方便计算我们开局直接把k kk减一。时间复杂度O ( n log d i s t ) O(n\log dist)O(nlogdist)空间复杂度O ( d i s t ) O(dist)O(dist)AC代码C/* * LastEditTime: 2026-02-03 22:11:11 */typedeflonglongll;classSolution{public:llminimumCost(vectorintnums,intk,intdist){k--;multisetllstage(nums.begin()1,nums.begin()dist2),candidate;ll ansaccumulate(nums.begin(),nums.begin()dist2,0ll);while(stage.size()k){intretiree*stage.rbegin();stage.erase(prev(stage.end()));ans-retiree;candidate.insert(retiree);}ll nowAnsans;for(intenddist2;endnums.size();end){intinnums[end],outnums[end-dist-1];// outmultisetll::iterator itcandidate.find(out);if(it!candidate.end()){candidate.erase(it);}else{stage.erase(stage.find(out));nowAns-out;}// inif(in*stage.rbegin()){stage.insert(in);nowAnsin;}else{candidate.insert(in);}// resizeif(stage.size()k-1){intnewActor*candidate.begin();candidate.erase(candidate.begin());stage.insert(newActor);nowAnsnewActor;}elseif(stage.size()k1){intretiree*stage.rbegin();stage.erase(prev(stage.end()));nowAns-retiree;candidate.insert(retiree);}ansmin(ans,nowAns);}returnans;}};#ifdefined(_WIN32)||defined(__APPLE__)/* [1,3,2,6,4,2] 3 3 5 */intmain(){string s;inta,b;while(cinsab){Solution sol;vectorintvstringToVector(s);coutsol.minimumCost(v,a,b)endl;}return0;}#endif同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源
