题解 | #炼金术士的药剂平衡#

题目链接

炼金术士的药剂平衡

题目描述

两位炼金术士各有 $N$ 种魔法材料，其魔力值分别由数组 $A$ 和 $B$ 表示。当两个数组在排序后完全相同时，称之为完美平衡。

他们可以执行“置换术”：交换一个来自 $A$ 的材料和一个来自 $B$ 的材料。每次操作的法力消耗为被交换的两种材料魔力值中的较小者，即 $\min(\text{魔力值}_A, \text{魔力值}_B)$ 。

任务是计算达成完美平衡所需的最小总法力。如果无法达到平衡，则输出 -1。

输入:

第一行是材料数量 $N$ 。
第二行是数组 $A$ 的 $N$ 个整数。
第三行是数组 $B$ 的 $N$ 个整数。

输出:

一个整数，代表最小总法力消耗。

解题思路

这是一个复杂的贪心问题。核心在于，除了直接交换两个釜中多余的材料，我们还可以利用一个全局最便宜的材料作为“中介”来降低成本。

1. 判断是否可能达到平衡

首先，完美平衡意味着最终两个釜的材料构成完全相同。因此，将两个釜的所有材料合并后，每种魔力值的材料总数必须是偶数，否则无法平均分配。我们可以用一个哈希表统计所有材料的总数，若有奇数则无解，返回 -1。

2. 确定需要交换的材料

如果可能平衡，我们可以计算出每个釜最终应有的材料构成（即每种材料总数的一半）。

通过比较当前数量和目标数量，我们可以找出釜 A 多出来的材料列表（ $surplus\_a$ ）和釜 B 多出来的材料列表（ $surplus\_b$ ）。
这两个列表的长度必然相等，这个长度就是需要进行的交换次数。

3. 计算最小交换成本 (核心贪心策略)

这是问题的关键。对于每一次交换，我们都有两种选择：

直接交换：从 $surplus\_a$ 中取一个材料 $x$ ，从 $surplus\_b$ 中取一个材料 $y$ ，直接交换，成本为 $\min(x, y)$ 。
间接交换：我们可以利用全局魔力值最低的材料（设为 $min\_val$ ）作为中介。将 $x$ 换出去的成本可以降为 $min\_val$ ，将 $y$ 换出去的成本也可以降为 $min\_val$ 。完成一次 A 与 B 之间的交换，通过中介的总成本是 $2 \cdot min\_val$ 。

为了最小化总成本，我们应该为每一次交换都独立地选择成本更低的那种方式。

最优配对：为了尽可能降低“直接交换”的成本，我们应该将 $surplus\_a$ 中较小的元素与 $surplus\_b$ 中较大的元素配对。这可以通过将一个列表升序排序，另一个降序排序来实现。
最终决策：将 $surplus\_a$ 升序排序， $surplus\_b$ 降序排序。然后遍历配对，对于每一对 $(a[i], b[i])$ ，本次交换的成本就是 $\min(\min(a[i], b[i]), 2 \cdot min\_val)$ 。
将所有交换的成本累加，即为最小总法力。

最终算法步骤：

用哈希表统计所有材料的总数和釜 A 的材料数，并找到全局 $min\_val$ 。
检查是否有材料总数为奇数，若有则返回 -1。
根据目标数（总数/2）和釜 A 的当前数，构建出 $surplus\_a$ 和 $surplus\_b$ 列表。
将 $surplus\_a$ 升序排序， $surplus\_b$ 降序排序。
遍历两个列表，累加每次交换的成本 $\min(\min(a[i], b[i]), 2 \cdot min\_val)$ 。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <algorithm>
#include <functional>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    map<long long, int> total_counts;
    map<long long, int> counts_a;
    long long min_val = -1;

    for (int i = 0; i < n; ++i) {
        long long val;
        cin >> val;
        total_counts[val]++;
        counts_a[val]++;
        if (min_val == -1 || val < min_val) min_val = val;
    }
    for (int i = 0; i < n; ++i) {
        long long val;
        cin >> val;
        total_counts[val]++;
        if (min_val == -1 || val < min_val) min_val = val;
    }

    for (auto const& [val, count] : total_counts) {
        if (count % 2 != 0) {
            cout << -1 << endl;
            return 0;
        }
    }

    vector<long long> surplus_a, surplus_b;
    for (auto const& [val, total_count] : total_counts) {
        int target = total_count / 2;
        int count_in_a = counts_a.count(val) ? counts_a[val] : 0;
        
        if (count_in_a > target) {
            for (int i = 0; i < (count_in_a - target); ++i) {
                surplus_a.push_back(val);
            }
        } else if (count_in_a < target) {
            for (int i = 0; i < (target - count_in_a); ++i) {
                surplus_b.push_back(val);
            }
        }
    }
    
    sort(surplus_a.begin(), surplus_a.end());
    sort(surplus_b.rbegin(), surplus_b.rend());
    
    long long total_cost = 0;
    for (size_t i = 0; i < surplus_a.size(); ++i) {
        long long direct_swap_cost = min(surplus_a[i], surplus_b[i]);
        long long indirect_swap_cost = 2 * min_val;
        total_cost += min(direct_swap_cost, indirect_swap_cost);
    }

    cout << total_cost << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        Map<Long, Integer> total_counts = new HashMap<>();
        Map<Long, Integer> counts_a = new HashMap<>();
        long min_val = -1;

        for (int i = 0; i < n; i++) {
            long val = sc.nextLong();
            total_counts.put(val, total_counts.getOrDefault(val, 0) + 1);
            counts_a.put(val, counts_a.getOrDefault(val, 0) + 1);
            if (min_val == -1 || val < min_val) min_val = val;
        }
        for (int i = 0; i < n; i++) {
            long val = sc.nextLong();
            total_counts.put(val, total_counts.getOrDefault(val, 0) + 1);
            if (min_val == -1 || val < min_val) min_val = val;
        }

        for (int count : total_counts.values()) {
            if (count % 2 != 0) {
                System.out.println(-1);
                return;
            }
        }

        List<Long> surplus_a = new ArrayList<>();
        List<Long> surplus_b = new ArrayList<>();

        for (Map.Entry<Long, Integer> entry : total_counts.entrySet()) {
            long val = entry.getKey();
            int total_count = entry.getValue();
            int target = total_count / 2;
            int count_in_a = counts_a.getOrDefault(val, 0);

            if (count_in_a > target) {
                for (int i = 0; i < (count_in_a - target); i++) {
                    surplus_a.add(val);
                }
            } else if (count_in_a < target) {
                for (int i = 0; i < (target - count_in_a); i++) {
                    surplus_b.add(val);
                }
            }
        }

        Collections.sort(surplus_a);
        surplus_b.sort(Collections.reverseOrder());

        long total_cost = 0;
        for (int i = 0; i < surplus_a.size(); i++) {
            long direct_swap_cost = Math.min(surplus_a.get(i), surplus_b.get(i));
            long indirect_swap_cost = 2 * min_val;
            total_cost += Math.min(direct_swap_cost, indirect_swap_cost);
        }

        System.out.println(total_cost);
    }
}

import collections

# 读取输入
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

total_counts = collections.Counter(a) + collections.Counter(b)
counts_a = collections.Counter(a)
min_val = min(min(a), min(b))


# 1. 检查是否可能平衡
for count in total_counts.values():
    if count % 2 != 0:
        print(-1)
        exit()

# 2. 确定需要交换的材料
surplus_a = []
surplus_b = []
for val, total_count in total_counts.items():
    target = total_count // 2
    count_in_a = counts_a.get(val, 0)
    
    if count_in_a > target:
        surplus_a.extend([val] * (count_in_a - target))
    elif count_in_a < target:
        surplus_b.extend([val] * (target - count_in_a))

# 3. 计算最小成本
surplus_a.sort()
surplus_b.sort(reverse=True)

total_cost = 0
indirect_swap_cost = 2 * min_val

for i in range(len(surplus_a)):
    direct_swap_cost = min(surplus_a[i], surplus_b[i])
    total_cost += min(direct_swap_cost, indirect_swap_cost)

print(total_cost)

算法及复杂度

算法：哈希表 + 贪心 + 排序
时间复杂度： $O(N \log N)$ ，主要瓶颈在于对需要交换的材料列表进行排序。哈希表的构建和遍历都是 $O(N)$ 。
空间复杂度： $O(N)$ ，用于存储哈希表和需要交换的材料列表。