思路

• 可行性判定

  • 对每个数值 $v$，合并出现次数 $cnt(v)=cnt_1(v)+cnt_2(v)$。若存在 $cnt(v)$ 为奇数，则无论如何交换都无法均衡，直接返回 $-1$。

• 需要交换的元素集合

  • 对每个数值 $v$，计算差值 $\Delta(v)=cnt_1(v)-cnt_2(v)$。
  • 若 $\Delta(v)>0$，向集合 $A$ 放入 $\Delta(v)/2$ 个 $v$（表示这些值需要从 $bms1$ 移出）。
  • 若 $\Delta(v)<0$，向集合 $B$ 放入 $-\Delta(v)/2$ 个 $v$（表示这些值需要从 $bms2$ 移出）。
  • 必有 $|A|=|B|=k$，且至少需要交换 $k$ 次。

• 最优配对与换法

  • 设全局最小值 $m=\min(\min(bms1),\min(bms2))$。

  • 对于一对待交换的元素 $(x\in A,\,y\in B)$，可直接交换代价为 $\min(x,y)$，也可通过最小元 $m$ 中转（两次跨箱交换），总代价为 $2m$。因此单对最优代价为

    $$\min(\min(x,y),\,2m).$$

  • 为最小化总代价，将 $A$ 升序、$B$ 降序配对，使每对的较小者尽量小，从而减小 $\min(x,y)$。

• 复杂度

  • 计数与构造集合：$O(M)$；排序：$O(M\log M)$；总复杂度 $O(M\log M)$，空间 $O(M)$。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M;
    if (!(cin >> M)) return 0;
    vector<long long> a(M), b(M);
    for (int i = 0; i < M; ++i) cin >> a[i];
    for (int i = 0; i < M; ++i) cin >> b[i];

    // 统计全局最小值m
    long long m = LLONG_MAX;
    for (auto &x : a) m = min(m, x);
    for (auto &x : b) m = min(m, x);

    // 分别统计两个数组中每个数的出现次数
    unordered_map<long long, long long> cnt1, cnt2, total;
    cnt1.reserve(M * 2); cnt2.reserve(M * 2); total.reserve(M * 2);
    for (auto &x : a) { cnt1[x]++; total[x]++; }
    for (auto &x : b) { cnt2[x]++; total[x]++; }

    // 可行性判定：合并次数必须为偶数
    for (auto &kv : total) {
        if ((kv.second & 1LL) != 0) {
            cout << -1 << "\n";
            return 0;
        }
    }

    // 构造需要移动的多重集合A、B
    vector<long long> A, B;
    A.reserve(M); B.reserve(M);
    for (auto &kv : total) {
        long long v = kv.first;
        long long d = cnt1[v] - cnt2[v]; // 可能为负
        if (d > 0) {
            long long t = d / 2;
            while (t--) A.push_back(v);
        } else if (d < 0) {
            long long t = (-d) / 2;
            while (t--) B.push_back(v);
        }
    }

    if (A.empty()) { // 已经均衡
        cout << 0 << "\n";
        return 0;
    }

    // 排序并配对：A升序，B降序
    sort(A.begin(), A.end());
    sort(B.begin(), B.end(), greater<long long>());

    // 计算最小总代价：sum min(min(A[i], B[i]), 2*m)
    unsigned long long ans = 0;
    for (size_t i = 0; i < A.size(); ++i) {
        unsigned long long direct = (unsigned long long)min(A[i], B[i]);
        unsigned long long viaMin = (unsigned long long)(2LL * m);
        ans += min(direct, viaMin);
    }

    cout << ans << "\n";
    return 0;
}

Python

import sys

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    M = int(next(it))
    a = [int(next(it)) for _ in range(M)]
    b = [int(next(it)) for _ in range(M)]

    # 全局最小值
    m = min(min(a), min(b))

    # 次数统计
    from collections import Counter
    cnt1 = Counter(a)
    cnt2 = Counter(b)
    total = cnt1 + cnt2  # 合并计数

    # 可行性判定：合并次数必须为偶数
    for v, c in total.items():
        if c % 2 != 0:
            print(-1)
            return

    # 构造A、B
    A, B = [], []
    for v in total.keys():
        d = cnt1.get(v, 0) - cnt2.get(v, 0)
        if d > 0:
            A.extend([v] * (d // 2))
        elif d < 0:
            B.extend([v] * ((-d) // 2))

    if not A:
        print(0)
        return

    A.sort()           # 升序
    B.sort(reverse=True)  # 降序

    # 计算总代价
    ans = 0
    two_m = 2 * m
    for x, y in zip(A, B):
        ans += min(min(x, y), two_m)

    print(ans)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

/*
  思路：
  - 统计两个数组内每个值的出现次数，并做合并计数；若某值合并次数为奇数则返回-1
  - 差值一半分别放入A和B，A表示需要从bms1移出的元素，B表示需要从bms2移出的元素
  - A升序，B降序配对；每对交换代价为 min(min(x, y), 2*m)
  - 复杂度 O(M log M)
*/
public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        Integer MObj = fs.nextInt();
        if (MObj == null) return;
        int M = MObj;

        long[] a = new long[M];
        long[] b = new long[M];
        for (int i = 0; i < M; i++) a[i] = fs.nextLong();
        for (int i = 0; i < M; i++) b[i] = fs.nextLong();

        long m = Long.MAX_VALUE;
        for (long x : a) m = Math.min(m, x);
        for (long x : b) m = Math.min(m, x);

        // 次数统计
        HashMap<Long, Long> cnt1 = new HashMap<>();
        HashMap<Long, Long> cnt2 = new HashMap<>();
        HashMap<Long, Long> total = new HashMap<>();
        for (long x : a) {
            cnt1.put(x, cnt1.getOrDefault(x, 0L) + 1);
            total.put(x, total.getOrDefault(x, 0L) + 1);
        }
        for (long x : b) {
            cnt2.put(x, cnt2.getOrDefault(x, 0L) + 1);
            total.put(x, total.getOrDefault(x, 0L) + 1);
        }

        // 可行性判定
        for (Map.Entry<Long, Long> e : total.entrySet()) {
            if ((e.getValue() & 1L) != 0L) {
                System.out.println(-1);
                return;
            }
        }

        ArrayList<Long> A = new ArrayList<>();
        ArrayList<Long> B = new ArrayList<>();
        for (Long v : total.keySet()) {
            long c1 = cnt1.getOrDefault(v, 0L);
            long c2 = cnt2.getOrDefault(v, 0L);
            long d = c1 - c2;
            if (d > 0) {
                long t = d / 2;
                for (int i = 0; i < t; i++) A.add(v);
            } else if (d < 0) {
                long t = (-d) / 2;
                for (int i = 0; i < t; i++) B.add(v);
            }
        }

        if (A.isEmpty()) {
            System.out.println(0);
            return;
        }

        // A升序
        Collections.sort(A);
        // B降序
        B.sort(Collections.reverseOrder());

        long twoM = 2L * m;
        long ans = 0L;
        for (int i = 0; i < A.size(); i++) {
            long x = A.get(i), y = B.get(i);
            long direct = Math.min(x, y);
            ans += Math.min(direct, twoM);
        }

        System.out.println(ans);
    }

    // 简单的快速输入
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        String next() throws IOException {
            StringBuilder sb = new StringBuilder();
            int c;
            while ((c = read()) != -1 && c <= ' ') {}
            if (c == -1) return null;
            do {
                sb.append((char)c);
                c = read();
            } while (c != -1 && c > ' ');
            return sb.toString();
        }
        Integer nextInt() throws IOException {
            String s = next();
            return s == null ? null : Integer.parseInt(s);
        }
        Long nextLong() throws IOException {
            String s = next();
            return s == null ? null : Long.parseLong(s);
        }
    }
}

题目内容

储能工厂在发货时，一次同时发两个储能集装箱。每个集装箱中均 $M$ 个电芯，用两个数组 $bms1，bms2$ 表示每个集箱中的电芯的电量，为了保证两个集装箱电芯电量的均衡，需要调整两个集装箱中的电芯，使得两个集装箱中的电芯电最完全均衡(根据集装箱中电芯的电量进行排序，如果排序后的结果完全相同，则认为两个集装箱的电芯电量完全均衡)。调整的代价如下：比如交换电芯 $bms1[i]和bms2[j]$，代价为 $min(bms1[i]，bms2[j])$ 。可以多次调整，请返回调整的最小代价。如果无法使得两个集装箱中的电芯电量完全均衡，返回 $-1$

输入描述

第一行是一个整数 $M$ ，表示集装箱内电芯的数量。$1 <= M <= 10^5$。

接下两行是长度均为 $M$ 的整数数组 $bms1$ 和 $bms2$ ，分别代表两个集装箱内电芯的电量

$1 <= bms1[i], bms2[j] <= 10^8$

输出描述

调整的代价(用例保证不会超过 $2^{64}$)

样例1

输入

4
4 5 6 3
5 4 6 2

输出

-1

说明

无论怎么调整，都无法使得两个储能柜的电芯相同

样例2

输入

5
5 2 3 5 6
2 3 3 3 6

输出

3

说明

交换 $bms1[0]$ 和 $bms2[1]$ ，代价为 $3$ ，交换后，$bms1=3$ $2$ $3$ $5$ $6$ ，$bms2=2$ $5$ $3$ $3$ $6$ ，排序后两个集装箱中的电芯电量完全相同，都是 $2$ $3$ $3$ $5$ $6$