Codeforces糖果橘子均衡问题两种解法输出差异问询

题目背景 #

有n份礼物，每份礼物包含若干糖果和橘子。每一步操作可以选择以下三种之一：

• 从某份礼物中吃1颗糖果
• 从某份礼物中吃1个橘子
• 从某份礼物中同时吃1颗糖果和1个橘子

要求通过最少步数，让所有礼物的糖果数量一致，橘子数量也一致。

正确解法代码 #

for _ in range(int(input())): 
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    mina = min(a)
    minb = min(b)
    nrm = 0
    for i in range(n):
        nrm = nrm + max(a[i] - mina, b[i] - minb)
    print(nrm)

我的解法代码 #

for _ in range(int(input())): 
    n = int(input())
    a = sorted(map(int, input().split()))
    b = sorted(map(int, input().split()))
    nrm = 0
    for i in range(n):
        nrm = nrm + max(a[i] - a[0], b[i] - b[0])
    print(nrm)

测试用例 #

5
3
3 5 6
3 2 3
5
1 2 3 4 5
5 4 3 2 1
3
1 1 1
2 2 2
6
1 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1
3
10 12 8
7 5 4

输出对比 #

• 正确解法输出：

6
16
0
4999999995
7

• 我的解法输出：

5
10
0
4999999995
6

差异原因分析 #

核心问题出在你对两个数组分别排序后，打乱了原有的礼物对应关系。

题目中，a[i]和b[i]是属于同一份礼物的糖果数和橘子数，必须一一对应处理。但你的解法把a和b分别排序后，a[i]和b[i]已经不再是同一份礼物的数值了，这就导致计算逻辑完全错误。

拿第一个测试用例举例：
原输入的a = [3,5,6]，b = [3,2,3]，对应三份礼物是：

1. 糖果3，橘子3
2. 糖果5，橘子2
3. 糖果6，橘子3

正确解法中，mina=3，minb=2，计算每份礼物的max(a[i]-3, b[i]-2)：

• 第一份：max(0, 1) = 1
• 第二份：max(2, 0) = 2
• 第三份：max(3, 1) = 3
  总和1+2+3=6，符合正确输出。

而你的解法把a排序成[3,5,6]，b排序成[2,3,3]，此时对应关系变成：

1. 糖果3，橘子2
2. 糖果5，橘子3
3. 糖果6，橘子3
   计算max(a[i]-3, b[i]-2)：

• 第一份：max(0,0)=0
• 第二份：max(2,1)=2
• 第三份：max(3,1)=3
  总和0+2+3=5，这就是你得到错误输出的原因。

第二个测试用例的差异也是同理：原a递增、b递减，分别排序后a和b都变成递增，对应关系完全错乱，导致计算出的总步数远小于正确值。

只有当a和b的排序顺序完全一致时（比如第三个测试用例，a全1、b全2；第四个测试用例a排序后和原顺序一致、b全1），你的解法才会和正确解法输出相同，但这只是巧合。

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