题目描述：
你有两个果篮，每个果篮中有 n 个水果。给你两个下标从 0 开始的整数数组 basket1 和 basket2 ，用以表示两个果篮中每个水果的交换成本。为了让两个果篮中水果的数量相等。为此，可以根据需要多次执行下述操作：
- 选中两个下标
i 和 j ，并交换 basket1 中的第 i 个水果和 basket2 中的第 j 个水果。 - 交换的成本是
min(basket1i,basket2j) 。
根据果篮中水果的成本进行排序，如果排序后结果完全相同，则认为两个果篮相等。
返回使两个果篮相等的最小交换成本，如果无法使两个果篮相等，则返回 -1 。
数据范围：
$1\le len \le 10^5$
题解：
可以考虑先统计出每个元素出现的次数，如果有元素是奇数次，说明无法通过交换使得两个果篮相等。
然后得到每个果篮需要交换的数组 $a_1, a_2$ ，其中 $a_1,a_2$ 的大小是相等的。考虑贪心操作，肯定是需要使用 $a_1$ 中最小的数交换 $a_2$ 中最大的数，对于 $a_2$ 来说同理。
可以对两个数组排序，然后看哪个数字的最小值比较小，就先交换哪个数组，依次交替进行。实际上就是将 $a_1$ 与 $a_2$ 拼接排序（长度为 $2\times m$ ），然后交换其中最小的 $m$ 个。
正确性：假设这 $m$ 个最小的数中 $a_1$ 有 $b$ 个，则 $a_2$ 有 $m - b$ 个， $a_1$ 中有 $m - b$ 个大的数， $a_2$ 有 $b$ 个大的数。可以将 $a_1$ 中 $b$ 个小的与 $a_2$ 中 $b$ 个大的交换， $a_2$ 中 $m - b$ 个小的与 $a_1$ 中 $m - b$ 个大的交换。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
const static long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const static long long mod = 1e9 + 7;
long long minCost(vector<int> &basket1, vector<int> &basket2)
{
unordered_map<int, int> mp, mp1;
int minx = INF;
for (auto &x : basket1)
{
mp[x]++;
mp1[x]++;
}
for (auto &x : basket2)
{
mp[x]++;
}
for (auto &[key, value] : mp)
{
minx = min(minx, key);
if (value & 1)
return -1;
}
vector<int> ans;
for (auto &[key, value] : mp)
{
int cnt = 0;
if (!mp1.count(key))
{
cnt = value / 2;
}
else
{
cnt = abs(mp1[key] - value / 2);
}
for (int i = 0; i < cnt; ++i)
{
ans.emplace_back(key);
}
}
sort(ans.begin(), ans.end());
long long ret = 0;
for (int i = 0, j = ans.size() - 1; i < j; ++i, --j)
{
ret += min(1ll * ans[i], 1ll * minx * 2);
}
return ret;
}
};
|