【排序 贪心】3107. 使数组中位数等于 K 的最少操作数

算法可以发掘本质,如:
一,若干师傅和徒弟互有好感,有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。
二,有无限多1X2和2X1的骨牌,某个棋盘若干格子坏了,如何在没有坏的格子放足够多骨牌。
三,某个单色图,1表示前前景,0表示后景色。每次操作可以将一个1,变成0。如何在最少得操作情况下,使得没有两个1相邻(四连通)。
四,若干路人,有些人是熟人,如何选出最多的人参加实验。为了避免熟人影响实验的效果,参加的人不能是熟人。
一二是二分图的最大匹配,三是二分图的最小点覆盖,四是二分图最大独立集。 而这三者是等效问题。

本文涉及知识点

排序 贪心

LeetCode 3107. 使数组中位数等于 K 的最少操作数

给你一个整数数组 nums 和一个 非负 整数 k 。一次操作中,你可以选择任一元素 加 1 或者减 1 。
请你返回将 nums 中位数 变为 k 所需要的 最少 操作次数。
一个数组的中位数指的是数组按非递减顺序排序后最中间的元素。如果数组长度为偶数,我们选择中间两个数的较大值为中位数。
示例 1:
输入:nums = [2,5,6,8,5], k = 4
输出:2
解释:我们将 nums[1] 和 nums[4] 减 1 得到 [2, 4, 6, 8, 4] 。现在数组的中位数等于 k 。
示例 2:
输入:nums = [2,5,6,8,5], k = 7
输出:3
解释:我们将 nums[1] 增加 1 两次,并且将 nums[2] 增加 1 一次,得到 [2, 7, 7, 8, 5] 。
示例 3:
输入:nums = [1,2,3,4,5,6], k = 4
输出:0
解释:数组中位数已经等于 k 了。

提示:
1 <= nums.length <= 2 * 105
1 <= nums[i] <= 109
1 <= k <= 109

贪心

n = nums.length ,无轮n 是奇数,还是偶数。 排序后,中为数的下标都是n/2。
操作次数: { m a x ( 0 , n u m s [ i ] − k ) i < n / 2 a b s ( n u m s [ i ] − k ) i = = n / 2 m a x ( 0 , k − n u m s [ i ] ) i > n / 2 操作次数:\begin{cases} max(0,nums[i]-k) && i < n/2 \\ abs(nums[i]-k) && i == n/2 \\ max(0,k - nums[i]) && i > n/2 \\ \end{cases} 操作次数: max(0,nums[i]k)abs(nums[i]k)max(0,knums[i])i<n/2i==n/2i>n/2
除一个数为K外,n/2个数小于等于k,显然选择最小的n/2个数来操作成本最低。
n - n/2 -1 个数大于等于k,显然选择最大(n - n/2-1)来操作。

代码

class Solution {
public:long long minOperationsToMakeMedianK(vector<int>& nums, int k) {sort(nums.begin(), nums.end());int index = nums.size() / 2;int i = 0;long long ret = 0;for (; i < index; i++) {ret += max(0, nums[i] - k);}ret += abs(nums[i] - k);for (i++; i < nums.size(); i++) {ret += max(0, k - nums[i]);}return ret;}
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C语言中抽象的编译和链接原理

今天04.12&#xff0c;身体小有不适&#xff0c;但是睡不着觉&#xff0c;秉着不能浪费时间的原则&#xff0c;现在就简单写一下有关我们C语言中编译和链接的大体过程吧&#xff0c;因为编译和链接是比较抽象的&#xff0c;而且内容是比较底层&#xff0c;我们这里就简单了解它…

Chatgpt掘金之旅—有爱AI商业实战篇|SEO 咨询业务|(十七)

演示站点&#xff1a; https://ai.uaai.cn 对话模块 官方论坛&#xff1a; www.jingyuai.com 京娱AI 一、AI技术创业在SEO 咨询业务有哪些机会&#xff1f; 人工智能&#xff08;AI&#xff09;技术作为当今科技创新的前沿领域&#xff0c;为创业者提供了广阔的机会和挑战。随…

策略模式(知识点)——设计模式学习笔记

文章目录 0 概念1 使用场景2 优缺点2.1 优点2.2 缺点 3 实现方式4 和其他模式的区别5 具体例子实现5.1 实现代码 0 概念 定义&#xff1a;定义一个算法族&#xff0c;并分别封装起来。策略让算法的变化独立于它的客户&#xff08;这样就可在不修改上下文代码或其他策略的情况下…

蓝桥杯 每天2题 day6

碎碎念&#xff1a;哇咔咔 要不是中间缺勤一天就圆满day7了&#xff01;最后一晚上&#xff01;写题复习哇咔咔 唉&#xff0c;睡了一觉就看不下去了&#xff0c;&#xff0c;&#xff0c;看看之前的笔记洗洗睡觉&#xff0c;&#xff0c;&#xff0c; 记得打印准考证带好东西…

Java面试篇9——并发编程

并发编程知识梳理 提示&#xff0c;此仅为面试&#xff0c;若想对线程有跟完整了解&#xff0c;请点击这里 提示&#xff1a;直接翻到最后面看面试真题&#xff0c;上面的为详解 面试考点 文档说明 在文档中对所有的面试题都进行了难易程度和出现频率的等级说明 星数越多代表…

LeetCode34:在排序数组中查找元素的第一个和最后一个位置(Java)

目录 题目&#xff1a; 题解&#xff1a; 方法一&#xff1a; 方法二&#xff1a; 题目&#xff1a; 给你一个按照非递减顺序排列的整数数组 nums&#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target&…

3D场景编辑方法——CustomNeRF

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 摘要Abstract文献阅读&#xff1a;3D场景编辑方法——CustomNeRF1、研究背景2、提出方法3、CustomNeRF3.1、整体框架步骤3.2、对特定问题的解决 4、实验结果5、总结…

一辆汽车的节拍时间是怎样的?

节拍时间&#xff0c;又称 takt time&#xff0c;是德语中“节奏”的意思。在汽车制造业中&#xff0c;它指的是按照客户需求和生产计划&#xff0c;生产一辆汽车所需的时间。这个时间是固定的&#xff0c;它决定了生产线上每个工序的操作速度和节奏&#xff0c;是生产线上所有…

配置交换机 SSH 管理和端口安全

实验1:配置交换机基本安全和 SSH管理 1、实验目的 通过本实验可以掌握&#xff1a; 交换机基本安全配置。SSH 的工作原理和 SSH服务端和客户端的配置。 2、实验拓扑 交换机基本安全和 SSH管理实验拓扑如图所示。 3、实验步骤 &#xff08;1&#xff09;配置交换机S1 Swit…

liunx系统发布.net core项目

liunx系统发布.net core项目 准备.net6程序运行环境部署nginx&#xff0c;通过一个地址既能访问web api&#xff0c;又能访问web项目有一个客户把web api放到docker中&#xff0c;想通过nginx转发&#xff0c;nginx也支持配置多个程序api接口的其它 liunx系统&#xff1a;cento…

SQL执行流程图文分析:从连接到执行的全貌

SQL执行总流程 下面就是 MySQL 执行一条 SQL 查询语句的流程&#xff0c;也从图中可以看到 MySQL 内部架构里的各个功能模块。 MySQL 的架构共分为两层&#xff1a;Server 层和存储引擎层&#xff0c; Server 层负责建立连接、分析和执行 SQL。MySQL 大多数的核心功能模块都在…

STM32利用软件I2C通讯读MPU6050的ID号

今天的读ID号是建立在上篇文章中有了底层的I2C通讯的6个基本时序来编写的。首先需要完成的就是MPU6050的初始化函数 然后就是编写 指定地址写函数&#xff1a; 一&#xff1a;开始 二&#xff1a;发送 从机地址读写位&#xff08;1&#xff1a;读 0&#xff1…

Eureka-搭建Eureka步骤

简介&#xff1a; Eureka是Netflix开发的服务发现框架&#xff0c;本身是一个基于REST的服务&#xff0c;主要用于定位运行在AWS域中的中间层服务&#xff0c;以达到负载均衡和中间层服务故障转移的目的。SpringCloud将它集成在其子项目spring-cloud-netflix中&#xff0c;以实…

ReactRouter

React-Router 概念&#xff1a;一个路劲path对应一个组件component 当我们在浏览器中访问一个path的时候&#xff0c;path对应的组件会在页面中进行渲染路由语法&#xff1a; import {createBrowserRouter, RouterProvider} from react-router-dom// 1. 创建router实例对象并…

ArcGIS Desktop使用入门(三)图层右键工具——标注要素、将标注转换为注记

系列文章目录 ArcGIS Desktop使用入门&#xff08;一&#xff09;软件初认识 ArcGIS Desktop使用入门&#xff08;二&#xff09;常用工具条——标准工具 ArcGIS Desktop使用入门&#xff08;二&#xff09;常用工具条——编辑器 ArcGIS Desktop使用入门&#xff08;二&#x…

解决vue3更新chunk包后,点击页面报错

出现错误 解决思路 试了好多方法&#xff0c;跳了很多坑&#xff0c;router版本对不上&#xff0c;解决方案不实用。最后我直接捕获异常&#xff0c;刷新页面&#xff0c;解决最快最有效。 // vue-rotuer版本 "vue-router": "^4.0.3"解决方案 在router/…

数模 初见数建

文章目录 初见数学建模1.1 数学建模是什么1.2 数学建模的概述1.3 如何学习数学建模---分模块化1.4 数学建模前提了解1.5 数学建模的六个步骤1.6 如何备战建模比赛1.7 数学建模赛题类型1.8 数学建模算法体系概述 初见数学建模 1.1 数学建模是什么 1.原型与模型 原型&#xff…

5G Frequency Bands 频率分布

连接&#xff1a;https://www.5g-networks.net/5g-technology/5g-frequency-bands/

【Canvas与艺术】绘制黄色三角生化危险标志

【关键点】 系统函数arcTo函数的用法及自编函数createRegTriArr的灵活运用。 【成果图】 【代码】 <!DOCTYPE html> <html lang"utf-8"> <meta http-equiv"Content-Type" content"text/html; charsetutf-8"/> <head>&…

相机参数的意义

相机标定的意义&#xff1a; 相机标定&#xff1a;使用带有pattern的标定板来求解相机参数的过程&#xff1b;用一个简化的数学模型来代表复杂的三维到二维的成像过程&#xff1b;相机参数包括&#xff1a;相机内参&#xff08;焦距等&#xff09;&#xff0c;外参&#xff08…