算法可以发掘本质,如:
一,若干师傅和徒弟互有好感,有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。
二,有无限多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,k−nums[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++**实现。