求N张双面卡牌的最小Z值问题求助（可移动翻转卡牌）

问题描述 #

给定N张卡牌，每张卡牌的两面均为整数。定义Z = {卡牌1} - {卡牌2} + {卡牌3} - … + {卡牌n}，允许移动卡牌顺序和翻转任意卡牌，要求计算Z的最小值。

示例：当N=6，卡牌为[[-8, 12], [0, 5], [7, -3], [1, 4], [10, -7], [-2, 7]]时，Z的最小值为-34，对应取值为(-8) - 5 + (-3) - 7 + (-7) - 4。

错误解法分析 #

你尝试按卡牌两面数值之和降序排序，再交替选择使当前项最小的面，这种方法的问题在于：

• 局部最优（每一步选当前最小贡献）无法保证全局最优，因为交替顺序限制了卡牌的位置分配，而题目允许自由调整卡牌顺序，我们可以更灵活地选择哪些卡牌放在+位置、哪些放在-位置。
• 该解法没有考虑到+位置的数量是固定的（ceil(N/2)个），而是机械地按排序后的顺序交替分配符号，导致无法得到全局最小总和。

正确解法思路 #

我们可以将问题转化为选择固定数量的卡牌放在+位置，其余放在-位置，同时为每张卡牌选择最优的面，最终让总和最小：

1. 确定+位置的数量：k = (N + 1) // 2（因为Z的符号序列是+、-、+、-…，第一个位置为+，所以+位置的数量是N的向上取整）。
2. 对于每张卡牌：
   • 如果放在-位置，要让Z尽可能小，应该选择卡牌两面的最大值（因为Z是减去这个值，减去越大的数，Z越小），对应贡献为-max(a, b)。
   • 如果放在+位置，要让Z尽可能小，应该选择卡牌两面的最小值，对应贡献为min(a, b)。
3. 计算将一张卡牌从-位置切换到+位置时的总和变化量：delta = min(a, b) - (-max(a, b)) = a + b（因为min(a,b)+max(a,b)=a+b）。
4. 初始时，假设所有卡牌都放在-位置，总和为sum(-max(a,b) for all cards)。我们需要从中选k张卡牌切换到+位置，为了让总和最小，要选择变化量最小的k个delta（因为变化量越小，总和增加得越少，最终总和就越小）。
5. 最终的最小Z值 = 初始总和 + 最小的k个delta之和。

代码实现 #

def get_min_Z(cards):
    n = len(cards)
    k = (n + 1) // 2  # 需要放在+位置的卡牌数量
    total = 0
    deltas = []
    for a, b in cards:
        max_val = max(a, b)
        total -= max_val  # 初始都放在-位置，贡献是 -max_val
        delta = a + b  # 切换到+位置的变化量：min(a,b) - (-max_val) = (a+b - max_val) + max_val = a+b
        deltas.append(delta)
    # 选最小的k个delta加到total上
    deltas.sort()
    total += sum(deltas[:k])
    return total

# 测试示例
cards = [[-8, 12], [0, 5], [7, -3], [1, 4], [10, -7], [-2, 7]]
min_z = get_min_Z(cards)
print(min_z)  # 输出-34

验证示例 #

对示例中的卡牌：

• 初始总和（全放-位置）：-12 -5 -7 -4 -10 -7 = -45
• 所有delta值：4,5,4,5,3,5，排序后为3,4,4,5,5,5
• 取前3个最小的delta：3+4+4=11
• 最终总和：-45 +11 = -34，与示例结果一致。

内容的提问来源于stack exchange，提问作者Shirina