本文涉及的知识点
贪心 哈希映射 决策包容性
LeetCode2561. 重排水果
你有两个果篮,每个果篮中有 n 个水果。给你两个下标从 0 开始的整数数组 basket1 和 basket2 ,用以表示两个果篮中每个水果的交换成本。你想要让两个果篮相等。为此,可以根据需要多次执行下述操作:
选中两个下标 i 和 j ,并交换 basket1 中的第 i 个水果和 basket2 中的第 j 个水果。交换的成本是 min(basket1i,basket2j) 。
根据果篮中水果的成本进行排序,如果排序后结果完全相同,则认为两个果篮相等。
返回使两个果篮相等的最小交换成本,如果无法使两个果篮相等,则返回 -1 。
示例 1:
输入:basket1 = [4,2,2,2], basket2 = [1,4,1,2]
输出:1
解释:交换 basket1 中下标为 1 的水果和 basket2 中下标为 0 的水果,交换的成本为 1 。此时,basket1 = [4,1,2,2] 且 basket2 = [2,4,1,2] 。重排两个数组,发现二者相等。
示例 2:
输入:basket1 = [2,3,4,1], basket2 = [3,2,5,1]
输出:-1
解释:可以证明无法使两个果篮相等。
提示:
basket1.length == bakste2.length
1 <= basket1.length <= 105
1 <= basket1i,basket2i <= 109
看错题意(把最小交换成本看成min(i,j))贪心
哈希映射cnt记录各数出现的次数。如果任意数出现的次数是奇数,则返回-1。
哈希映射栈indexs1和indexs2 分别记录各数的下标。indexs1(indexs2)的元素x,出栈cnt[x]/2次。
将indexs1的剩余元素放到set1,将indexs2中的剩余元素放到set2中。就是两个数组要移出和交换的下标。
{ 移除 s e t 1 的最小元素,和 s e t 2 的最大元素 s e t 1 的最小元素小于 s e t 2 的最小元素 移除 s e t 2 的最小元素,和 s e t 1 的最大元素 o t h e r \begin{cases} 移除set1的最小元素,和set2的最大元素 && set1的最小元素小于set2的最小元素 \\ 移除set2的最小元素,和set1的最大元素 && other \end{cases} {移除set1的最小元素,和set2的最大元素移除set2的最小元素,和set1的最大元素set1的最小元素小于set2的最小元素other
下面用决策包容性来证明:
不失一般性,假定最小元素在set1,其最小元素为x1;set2中的最大元素为y2。假定某个方案x1不和y2交换。而是x1,y1交换,x2和y2交换。
某方案这两次交换的成本位:x1 + min(x2,y2)
贪心方案这两次交换的成本为:x1 + min(x2,y1)
由于y1 <= y2,故贪心方案不劣于任意方案,即每一步的最优解是全局最优解。
cnt[x]全为偶数一定有解
操作一:令x在第一个数组出现c1次,在第二个数组出现c2次。则本问题等效与 两个数组各删除min(c1,c2)个x。
由于c1+c2是偶数,x的剩余个数也为偶数。
操作一后:
两个数组元素数量仍然相等。因为每次删除相同的数。
任意数只会在一个数组出现。
两个数组元素数量为偶数。
操作二:
两个数组任选一个数,各删除两个。可以理解为:这4个数,均分。
操场二执行一次,两个数组元素数量都减少2,由于是偶数,且相等,故同时减为0。
贪心
第一个数组存在的元素x,cnt[x]++;第二个数组存在的元素x,cnt[x]–。有多少个x 执行多少次。
set1和set2要改成多键,会有重复的值。
如果cnt[x]为奇数,返回-1。
如果cnt[x]是正数,set1中增加cnt[x]/2。
如果cnt[x]是负数,set2中增加-cnt[x]/2个x。
如果cnt[x]为0,什么都不做。
优化
等效与set1和set2中最小一半数,可以用小根堆获取一半的最小数。
特殊情况间接交换可能比直接交换更划算,比如:
{8,32,32} {8,64,64}
分两步交换: 8 ↔ 32 64 ↔ 8 8\leftrightarrow32\quad 64\leftrightarrow8 8↔3264↔8 成本是16
一步交换: 32 ↔ 64 32 \leftrightarrow 64 32↔64 交换成本是32
即min(heap.top(),iMin*2)
iMin是两个数组的最小数。
代码
核心代码
class Solution {
public:
long long minCost(vector<int>& basket1, vector<int>& basket2) {
unordered_map<int, int> cnt;
for (const auto& n : basket1) {
cnt[n]++;
}
for (const auto& n : basket2) {
cnt[n]--;
}
priority_queue<int, vector<int>, greater<>> heap;
for (auto [x, c] : cnt) {
if (1 & c) { return -1; }
c = abs(c / 2);
while (c--) {
heap.emplace(x);
}
}
const int iMin1 = *std::min_element(basket1.begin(), basket1.end());
const int iMin2 = *std::min_element(basket2.begin(), basket2.end());
long long ret = 0;
for (int i = heap.size() / 2; i > 0; i--) {
ret += min(heap.top(), min(iMin1, iMin2) * 2);
heap.pop();
}
return ret;
}
};
单元测试
namespace UnitTest
{
vector<int> basket1, basket2;
TEST_CLASS(UnitTest)
{
public:
TEST_METHOD(TestMethod0)
{
basket1 = { 4, 2, 2, 2 }, basket2 = { 1, 4, 1, 2 };
auto res = Solution().minCost(basket1, basket2);
AssertEx(1LL, res);
}
TEST_METHOD(TestMethod1)
{
basket1 = { 2,3,4,1 }, basket2 = { 3,2,5,1 };
auto res = Solution().minCost(basket1, basket2);
AssertEx(-1LL, res);
}
TEST_METHOD(TestMethod2)
{
basket1 = { 84,80,43,8,80,88,43,14,100,88 }, basket2 = { 32,32,42,68,68,100,42,84,14,8 };
auto res = Solution().minCost(basket1, basket2);
AssertEx(48LL, res);
}
TEST_METHOD(TestMethod4)
{
basket1 = { 3350,1104,2004,1577,1365,2088,2249,1948,2621,750,31,2004,1749,3365,3350,3843,3365,1656,3168,3106,2820,3557,1095,2446,573,2464,2172,1326,2712,467,1104,1446,1577,53,2492,2638,1200,2997,3454,2492,1926,1452,2712,446,2997,2820,750,2529,3847,656,272,3873,530,1749,1743,251,3847,31,251,515,2858,126,2491 },
basket2 = { 530,1920,2529,2317,1969,2317,1095,2249,2858,2636,3772,53,3106,2638,1267,1926,2882,515,3772,1969,3454,2446,656,2621,1365,1743,3557,1656,3447,446,1098,1446,467,2636,1088,1098,2882,1088,1326,644,3873,3843,3926,1920,2464,2088,205,1200,1267,272,925,925,2172,2491,3168,644,1452,573,1948,3926,205,126,3447 };
auto res = Solution().minCost(basket1, basket2);
AssertEx(837LL, res);
}
};
}
扩展阅读
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关推荐
我想对大家说的话 |
---|
《喜缺全书算法册》以原理、正确性证明、总结为主。 |
按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。