【教3妹学编程-算法题】将数组分成最小总代价的子数组 II

瑟瑟发抖

2哥 : 叮铃铃,3妹,过年干嘛呢,是不是逛吃逛吃,有没有长胖呢。
3妹:切,我妈张罗着要给我相亲呢。
2哥 : 相亲?哈哈哈哈
3妹:别笑了,我妈说跟我年龄相等的人都已经孩子上小学了,跟她年龄相等的人孙子最少都会打酱油了。
2哥 :哈哈哈哈,让我先笑一会儿
3妹:话说2哥过年在家里也刷题吗?
2哥:当然了,雷打不动。
3妹:好吧,还得是2哥🐂,我有几天懈怠了。
2哥:好吧,说到刷题啊,今天有一道“最小”的题目, 让我们先做一下吧~

吃瓜

题目:

给你一个下标从 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 <= 10^5
1 <= nums[i] <= 10^9
3 <= k <= n
k - 2 <= dist <= n - 2

思路:

思考

维护两个有序集合前K-1小的数,
第一段的第一个数是确定的,即 nums[0]。

如果知道了第二段的第一个数的位置(记作 p),第三段的第一个数的位置,……,第 k 段的第一个数的位置(记作 q),那么这个划分方案也就确定了。

考虑到 q−p≤dist,本题相当于在一个大小固定为 dist+1的滑动窗口内,求前 k−1 小的元素和。

java代码:

public class Solution {
    public long minimumCost(int[] nums, int k, int dist) {
        k--;
        sumL = nums[0];
        for (int i = 1; i < dist + 2; i++) {
            sumL += nums[i];
            L.merge(nums[i], 1, Integer::sum);
        }
        sizeL = dist + 1;
        while (sizeL > k) {
            l2r();
        }

        long ans = sumL;
        for (int i = dist + 2; i < nums.length; i++) {
            // 移除 out
            int out = nums[i - dist - 1];
            if (L.containsKey(out)) {
                sumL -= out;
                sizeL--;
                removeOne(L, out);
            } else {
                removeOne(R, out);
            }

            // 添加 in
            int in = nums[i];
            if (in < L.lastKey()) {
                sumL += in;
                sizeL++;
                L.merge(in, 1, Integer::sum);
            } else {
                R.merge(in, 1, Integer::sum);
            }

            // 维护大小
            if (sizeL == k - 1) {
                r2l();
            } else if (sizeL == k + 1) {
                l2r();
            }

            ans = Math.min(ans, sumL);
        }
        return ans;
    }

    private long sumL;
    private int sizeL;
    private final TreeMap<Integer, Integer> L = new TreeMap<>();
    private final TreeMap<Integer, Integer> R = new TreeMap<>();

    private void l2r() {
        int x = L.lastKey();
        removeOne(L, x);
        sumL -= x;
        sizeL--;
        R.merge(x, 1, Integer::sum);
    }

    private void r2l() {
        int x = R.firstKey();
        removeOne(R, x);
        sumL += x;
        sizeL++;
        L.merge(x, 1, Integer::sum);
    }

    private void removeOne(Map<Integer, Integer> m, int x) {
        int cnt = m.get(x);
        if (cnt > 1) {
            m.put(x, cnt - 1);
        } else {
            m.remove(x);
        }
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/388995.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

iptables防火墙、filter表控制、扩展匹配、使用iptables配置网络型防火墙、NAT原理、配置SNAT

目录 iptables 防火墙filter表 filter中的三条链 环境准备 iptables操作 验证FORWARD链 准备环境 配置FORWARD链 NAT 配置SNAT iptables iptables有多种功能&#xff0c;每一种功能都用一张表来实现最常用的功能是防火墙和NAT从RHEL7开始&#xff0c;默认的防火墙为…

.NET Core WebAPI中使用swagger版本控制,添加注释

一、效果 二、实现步骤 在代码中添加注释 在项目属性中生成API文档 在Program中注册Swagger服务并配置文档信息 // 添加swagger注释 builder.Services.AddSwaggerGen(x > {x.SwaggerDoc("v1", new OpenApiInfo { Title "Swagger标题", Version "…

STM32F1 - 中断系统

Interrupt 1> 硬件框图2> NVIC 中断管理3> EXTI 中断管理3.1> EXTI与NVIC3.2> EXTI内部框图 4> 外部中断实验4.1> 实验概述4.2> 程序设计 5> 总结 1> 硬件框图 NVIC&#xff1a;Nested Vectored Interrupt Controller【嵌套向量中断控制器】 管理…

springboot192中国陕西民俗网

简介 【毕设源码推荐 javaweb 项目】基于springbootvue 的中国陕西民俗网 适用于计算机类毕业设计&#xff0c;课程设计参考与学习用途。仅供学习参考&#xff0c; 不得用于商业或者非法用途&#xff0c;否则&#xff0c;一切后果请用户自负。 看运行截图看 第五章 第四章 获取…

蓝桥杯:C++排列与组合

排列是暴力枚举时的常见操作。有以下两种情况。 C的 next_permutation()是全排列函数&#xff0c;只能输出序列中所有元素的全排列。 本节将给出手写排列和组合的代码。因为在很多场合中不能使用系统自带的排列函数&#xff0c;所以需要自己编写。 全排列函数&#xff1a;nex…

《合成孔径雷达成像算法与实现》Figure6.18

% rho_r c/(2*Fr)而不是rho_r c/(2*Bw) % Hsrcf exp函数里忘记乘pi了 clc clear close all参数设置 距离向参数设置 R_eta_c 20e3; % 景中心斜距 Tr 2.5e-6; % 发射脉冲时宽 Kr 20e12; % 距离向调频率 alpha_os_r 1.2; …

如何使用六图一表七种武器

六图一表七种武器用于质量管理&#xff1a; 描述当遇到问题时应该用那张图来解决&#xff1a; 一、如果题目说出了质量问题需要找原因&#xff1f; 解&#xff1a;用因果图&#xff0c;因果图也称石川图或鱼骨图 二、如果要判断过程是否稳定受控&#xff1f; 解&#xff1a…

【zabbix】(五)-自定义监控项:MySQL主从状态-自动告警

一 查看主从状态 二 在zabbix-agent端配置监控脚本 2.1 首先定义监控项 [rootmysql-112 conf]# mysql -uroot -pLXYlxy2:024.#8u} -e "show slave status\G" | grep -w Slave_IO_Running | awk {print $2} mysql: [Warning] Using a password on the command line…

UI设计常见风格(1):一文读懂九个,教你如何辨识。

Hello&#xff0c;我是大千UI工场&#xff0c;设计风格是我们新开辟的栏目&#xff0c;上次讲了毛玻璃风格、辨识方法、应用场景、运用方法等&#xff0c;很受大家欢迎&#xff0c;本次带来常见的风格及辨识&#xff0c;让大家有个总览&#xff0c;以后会逐个讲解的&#xff0c…

Python一些可能用的到的函数系列124 GlobalFunc

说明 GlobalFunc是算网的下一代核心数据处理基础。 算网是一个分布式网络&#xff0c;为了能够实现真的分布式计算&#xff08;加快大规模任务执行效率&#xff09;&#xff0c;以及能够在很长的时间内维护不同版本的计算方法&#xff0c;需要这样一个对象/服务来支撑。Globa…

学法减分线上考试答案查找?分享九个搜题直接出答案的软件 #媒体#媒体#笔记

在信息爆炸的时代&#xff0c;选择适合自己的学习辅助工具和资料&#xff0c;能够提供更高效、便捷和多样化的学习方式。 1.试题猪 这是个微信公众号 一款聚合了好多款搜题软件的公众号&#xff0c;对话框可以直接搜题&#xff0c;题库好像挺多的&#xff0c;一次性能出好多…

计算机二级数据库之数据模型(三层相关的结构)

数据模型 模型的概念 模型的介绍模型是对现实世界特征的模拟和抽象&#xff0c; 数据模型的概念&#xff1a; 数据模型是对现实世界中数据特征的抽象&#xff0c;描述的是数据的共性。 数据模型是用来在数据库中抽象、表示和处理现实世界中的数据和信凹。 其相关的共同特…

阿里云幻兽帕鲁服务器中据点帕鲁数量上限是修改哪个参数?

在阿里云的计算巢管理中&#xff0c;找到你的这台部署幻兽帕鲁的服务器实例&#xff0c;选择右上角的“修改游戏配置” 然后选择“基地内工作帕鲁的最大数量”改成20 不过也有同学说更改上面的数字&#xff0c;根本不起作用。 参考资料&#xff1a;大多数人现在都知道&#xf…

AGV|RGV基本概念及导航分类与差异

AGV是自动导引运输车&#xff0c;装备采用电磁或光学等自动导引装置&#xff0c;能够沿规定的导引路径行驶&#xff0c;具有安全保护以及各种移载功能的运输车。其导航方式主要分磁条|磁钉导航、激光导航、激光反光板、激光自然导航、二维码导航、惯性导航等方式&#xff0c;广…

【51单片机】利用STC-ISP软件工具【定时器计算器】配置【定时器】教程(详细图示)(AT89C52)

前言 大家好吖&#xff0c;欢迎来到 YY 滴单片机系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过单片机的老铁 主要内容含&#xff1a; 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; YY的《C》专栏YY的《C11》专栏YY的…

OpenAI全新发布文生视频模型Sora - 现实,不存在了

OpenAI&#xff0c;发他们的文生视频大模型&#xff0c;Sora了。。。。。 而且&#xff0c;是强到&#xff0c;能震惊我一万年的程度。。。 https://openai.com/sora 如果非要用三个词来总结Sora&#xff0c;那就是“60s超长长度”、“单视频多角度镜头”和“世界模型” &am…

一周学会Django5 Python Web开发-项目配置settings.py文件-资源文件配置

锋哥原创的Python Web开发 Django5视频教程&#xff1a; 2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~共计17条视频&#xff0c;包括&#xff1a;2024版 Django5 Python we…

深度学习之梯度下降算法

梯度下降算法 梯度下降算法数学公式结果 梯度下降算法存在的问题随机梯度下降算法 梯度下降算法 数学公式 这里案例是用梯度下降算法&#xff0c;来计算 y w * x 先计算出梯度&#xff0c;再进行梯度的更新 import numpy as np import matplotlib.pyplot as pltx_data [1.0,…

紫微斗数双星组合:武曲破军在巳亥

文章目录 前言内容总结 前言 紫微斗数双星组合&#xff1a;武曲破军在巳亥 内容 紫微斗数双星组合&#xff1a;武曲破军在巳亥 性格分析 在紫微斗数命盘中&#xff0c;武曲星入命之人性格大都为正直、刚强、果决、重视原则。假如与破军星同守命宫时&#xff0c;身边的破军是…

【防网盘在线解压】Peazip 豌豆压缩 v9.7.0

软件介绍 Peazip 是一个免费的文件归档应用程序&#xff0c; 支持跨平台&#xff0c;是和WinRar、WinZip类似软件的开源免费替代品&#xff1b;支持压缩/ 存档到 7Z&#xff0c; ARC、Brotli BR、BZip2、GZip、 PAQ、PEA、RAR、自解压档案、TAR、WIM、XZ、Zstandard ZST、打开…