解题思路

• 把两个核心上的进程负载分别记为数组 cpu1[]、cpu2[]。若将两数组排序后完全相同，则称达到“负载平衡”。

• 交换一次的功耗为两被交换任务负载的较小值。

• 关键观察与算法：

  1. 计数判定：将两数组所有数值做频次统计，若某个负载在两数组合并后的出现次数为奇数，则无法分成两半，返回 -1。

  2. 构造需要互换的多重集合：对每个负载 v，目标是让两个数组中 v 的个数都为 total[v]/2。 多出的放入 Aextra（来自 cpu1），缺的放入 Bextra（来自 cpu2，用等价的“多出”表示）。两个集合大小相等。

  3. 贪心配对 + 中转优化：

     • 将 Aextra 升序，Bextra 降序，一一配对交换，可使直接交换代价为 min(x, y) 的和最小。
     • 允许通过全局最小值 g = min(all elements) 作为“中转”来降低代价（两次交换），该方案代价为 2*g。 因此每一对的最小代价为 min( min(x, y), 2*g )。

• 将上述代价累加即为答案；若本就已平衡则答案为 0。

复杂度分析

• 设进程数为 n。
• 频次统计与构造集合：O(n)；排序与配对：O(k log k)（k 为需要交换的对数，k ≤ n）。
• 总时间复杂度 O(n log n)，空间复杂度 O(n)，满足数据范围。

代码实现

Python

# 题面功能在外部函数里，主函数只负责读写
import sys
from collections import Counter
from ast import literal_eval

def parse_line(s: str):
    """优先用 literal_eval；失败则按常见分隔符处理"""
    s = s.strip()
    if not s:
        return []
    try:
        arr = literal_eval(s)
        if isinstance(arr, (list, tuple)):
            return list(map(int, arr))
    except Exception:
        pass
    for ch in "[],;":
        s = s.replace(ch, " ")
    return [int(x) for x in s.split()]

def min_energy(a, b) -> int:
    """返回最小功耗；若无法平衡返回 -1"""
    cntA = Counter(a)
    cntB = Counter(b)
    total = cntA + cntB

    # 若某负载总数为奇数，则无法平衡
    for v, c in total.items():
        if c % 2 == 1:
            return -1

    half = {v: c // 2 for v, c in total.items()}
    Aextra, Bextra = [], []
    for v in total:
        diff = cntA.get(v, 0) - half[v]
        if diff > 0:
            Aextra.extend([v] * diff)
        elif diff < 0:
            Bextra.extend([v] * (-diff))

    if not Aextra:  # 已经平衡
        return 0

    Aextra.sort()             # 升序
    Bextra.sort(reverse=True) # 降序
    g = min(min(a), min(b))   # 全局最小值

    ans = 0
    for x, y in zip(Aextra, Bextra):
        ans += min(min(x, y), 2 * g)
    return ans

def main():
    lines = [ln for ln in sys.stdin.read().strip().splitlines() if ln.strip()]
    if len(lines) < 2:
        print(0)
        return
    a = parse_line(lines[0])
    b = parse_line(lines[1])
    print(min_energy(a, b))

if __name__ == "__main__":
    main()

Java

// 类名必须为 Main，ACM 风格：主函数处理输入输出，算法写在静态函数里
import java.io.*;
import java.util.*;

public class Main {

    // 计算最小功耗；无法平衡返回 -1
    static long minEnergy(int[] a, int[] b) {
        Map<Integer, Integer> cntA = new HashMap<>();
        Map<Integer, Integer> cntB = new HashMap<>();
        for (int x : a) cntA.put(x, cntA.getOrDefault(x, 0) + 1);
        for (int x : b) cntB.put(x, cntB.getOrDefault(x, 0) + 1);

        Map<Integer, Integer> total = new HashMap<>();
        for (Map.Entry<Integer, Integer> e : cntA.entrySet())
            total.put(e.getKey(), total.getOrDefault(e.getKey(), 0) + e.getValue());
        for (Map.Entry<Integer, Integer> e : cntB.entrySet())
            total.put(e.getKey(), total.getOrDefault(e.getKey(), 0) + e.getValue());

        // 奇数频次则无解
        for (int v : total.keySet()) {
            if ((total.get(v) & 1) == 1) return -1L;
        }

        Map<Integer, Integer> half = new HashMap<>();
        for (Map.Entry<Integer, Integer> e : total.entrySet())
            half.put(e.getKey(), e.getValue() / 2);

        List<Integer> Aextra = new ArrayList<>();
        List<Integer> Bextra = new ArrayList<>();
        for (int v : total.keySet()) {
            int diff = cntA.getOrDefault(v, 0) - half.get(v);
            if (diff > 0) {
                for (int i = 0; i < diff; i++) Aextra.add(v);
            } else if (diff < 0) {
                for (int i = 0; i < -diff; i++) Bextra.add(v);
            }
        }

        if (Aextra.isEmpty()) return 0L;

        Collections.sort(Aextra);                    // 升序
        Bextra.sort(Collections.reverseOrder());     // 降序

        int g = Integer.MAX_VALUE;
        for (int x : a) g = Math.min(g, x);
        for (int x : b) g = Math.min(g, x);

        long ans = 0L;
        for (int i = 0; i < Aextra.size(); i++) {
            int x = Aextra.get(i), y = Bextra.get(i);
            ans += Math.min(Math.min(x, y), 2L * g);
        }
        return ans;
    }

    // 将一行如 "[4,2,2,4]" 或 "4 2 2 4" 转成 int[]
    static int[] parseLine(String s) {
        s = s.trim();
        s = s.replace('[', ' ').replace(']', ' ')
             .replace(',', ' ').replace(';', ' ');
        if (s.isEmpty()) return new int[0];
        String[] parts = s.split("\\s+");
        int[] arr = new int[parts.length];
        for (int i = 0; i < parts.length; i++) arr[i] = Integer.parseInt(parts[i]);
        return arr;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String l1 = br.readLine();
        String l2 = br.readLine();
        int[] a = parseLine(l1 == null ? "" : l1);
        int[] b = parseLine(l2 == null ? "" : l2);
        System.out.println(minEnergy(a, b));
    }
}

C++

// ACM 风格：主函数读写，核心逻辑在独立函数中
#include <bits/stdc++.h>
using namespace std;

// 计算最小功耗；无法平衡返回 -1
long long minEnergy(const vector<long long>& a, const vector<long long>& b) {
    unordered_map<long long, long long> cntA, cntB, total;
    for (auto x : a) cntA[x]++, total[x]++;
    for (auto x : b) cntB[x]++, total[x]++;

    // 奇数频次则无解
    for (auto &kv : total) if (kv.second % 2 == 1) return -1;

    unordered_map<long long, long long> half;
    for (auto &kv : total) half[kv.first] = kv.second / 2;

    vector<long long> Aextra, Bextra;
    for (auto &kv : total) {
        long long v = kv.first;
        long long diff = (long long)cntA[v] - half[v];
        if (diff > 0) Aextra.insert(Aextra.end(), diff, v);
        else if (diff < 0) Bextra.insert(Bextra.end(), -diff, v);
    }

    if (Aextra.empty()) return 0;

    sort(Aextra.begin(), Aextra.end());                // 升序
    sort(Bextra.begin(), Bextra.end(), greater<>());   // 降序

    long long g = LLONG_MAX;
    for (auto x : a) g = min(g, x);
    for (auto x : b) g = min(g, x);

    long long ans = 0;
    for (size_t i = 0; i < Aextra.size(); ++i) {
        long long x = Aextra[i], y = Bextra[i];
        ans += min(min(x, y), 2 * g); // 直接交换或经全局最小值中转
    }
    return ans;
}

// 将一行如 "[4,2,2,4]" 或 "4 2 2 4" 转为数组
vector<long long> parseLine(string s) {
    for (char &c : s) {
        if (c == '[' || c == ']' || c == ',' || c == ';') c = ' ';
    }
    stringstream ss(s);
    vector<long long> v; long long x;
    while (ss >> x) v.push_back(x);
    return v;
}

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

    string l1, l2;
    if (!getline(cin, l1)) { cout << 0 << "\n"; return 0; }
    getline(cin, l2);
    vector<long long> a = parseLine(l1);
    vector<long long> b = parseLine(l2);

    cout << minEnergy(a, b) << "\n";
    return 0;
}

题目内容

在手机系统中，多核 $CPU$ 普遍应用于每个核心上运行的多个进程。

假设现在有两个 $CPU$ 核心，每个核心上运行了 $n$ 个进程，每个进程都有其各自的负载，记录在整数数组 $cpu1[]$ 和 $cpu2[]$ 中。

为了实现两个核心之间的负载平衡，需要将一些进程进行多次迁核交换，将运行在 $cpu1$ 上的进程与 $cpu2$ 上的进程进行交换，直到两个核心达到负载平衡，每次交换会消耗一定的功耗，功耗的具体计算是两个交换任务的负载的较小值。

这里负载平衡的定义是，两个核心上运行的进程按负载排序后，序列相同，即排序后，两个核心相同下标的负载相同请返回达到负载平衡所需的最小功耗值。如果无法达到负载平衡，请返回 $-1$ 。

输入描述

输入为两行，每一行都是个整数序列 $cpu1[]$ 和 $cpu2[]$ ，分别代表 $cpu1$ 和 $cpu2$ 上的进程负载参数范围:

1.进程个数 $n:1<=n<=10^5$

2.负载范围:$1<=cpu1[i]<=10^8,1<=cpu2[i]<=10^8$

输出描述

输出一个整数，代表达到负载平衡所需的最小功耗值，$-1$ 代表无法完成负载均衡

样例1

输入

4,2,2,4
2,1,1,2

输出

1

说明

$cpu1$ 的下标 $0$ 的元素 $4$ 和 $cpu2$ 下标 $1$ 的元素 $1$ 交换,产生功耗为 $1$ ，此时 $cpu1=[1,2,2,4],cpu2=[2,4,1,2]$ 排序后字列相同

样例2

输入

4,2,2
1,2,1

输出

-1

说明

无法完成负载均衡