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

package main

import (
	"fmt"
	"sort"
)

func min(a, b, c int) int {
	if a <=b && a <=c {
        return a
    } else if b <= a && b <= c {
        return b
    }
    return c
}

func solve(C1, C2 []int) int {
	// 合并并统计频次
	count := make(map[int]int)
    globalMin := C1[0]
	for _, x := range C1 {
		count[x]++
        if x < globalMin {
            globalMin = x
        }
	}
	for _, x := range C2 {
		count[x]++
        if x < globalMin {
            globalMin = x
        }
	}

	// 检查是否所有频次为偶数
	for _, cnt := range count {
		if cnt%2 != 0 {
			return -1
		}
	}

	// 构造目标：每个值出现 cnt/2 次
	target := []int{}
	for x, cnt := range count {
		for i := 0; i < cnt/2; i++ {
			target = append(target, x)
		}
	}
	sort.Ints(target)

	// 统计 C1 中每个值的实际频次
	cnt1 := make(map[int]int)
	for _, x := range C1 {
		cnt1[x]++
	}

	// 找出 C1 中多出的元素
	excess1 := []int{}
	for _, x := range target {
		if cnt1[x] > 0 {
			cnt1[x]--
		} else {
			excess1 = append(excess1, x)
		}
	}

	// C2 同理
	cnt2 := make(map[int]int)
	for _, x := range C2 {
		cnt2[x]++
	}
	excess2 := []int{}
	for _, x := range target {
		if cnt2[x] > 0 {
			cnt2[x]--
		} else {
			excess2 = append(excess2, x)
		}
	}

	// 应该相等
	if len(excess1) != len(excess2) {
		return -1 // 理论上不会发生
	}

	k := len(excess1)
	if k == 0 {
		return 0
	}

	// 贪心配对：排序后一一配对
	sort.Ints(excess1) // 升序
	sort.Sort(sort.Reverse(sort.IntSlice(excess2))) // 逆序

	cost := 0
	for i := 0; i < k; i++ {
		cost += min(2*globalMin, excess1[i], excess2[i]) // 小配大，或中介
	}

	return cost
}

func main() {
	var M int
	fmt.Scanf("%d", &M)

	C1 := make([]int, M)
	C2 := make([]int, M)

	for i := 0; i < M; i++ {
		fmt.Scanf("%d", &C1[i])
	}
	for i := 0; i < M; i++ {
		fmt.Scanf("%d", &C2[i])
	}

	result := solve(C1, C2)
	fmt.Println(result)
}