Codeforces中有一个问题正在谈论“均衡n个礼物中糖果和橙子的数量。你可以在一个动作中从每个礼物中吃一颗糖果或一个橙子或一颗糖果和一个橘子。你需要找到使所有被给予的礼物相等所需的最小移动次数。”这个问题的正确解决方案是这样的
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
1条答案
按热度按时间nbysray51#
你没有考虑到一起拿走一个糖果和一个橙子只是一步。
下面是第二种方法可能出错的一个简单例子。假设以下数据:
[0, 0, 10]
用于糖果,[0, 10, 0]
用于橙子。目标值现在是0个糖果和0个橙子。第一种方法将给予以下步数:
[0, 10, 10]
。这些加起来是20
。在第二种方法中,首先对数据进行排序。现在糖果有
[0, 0, 10]
,橙子有[0, 0, 10]
。这将导致以下移动次数:[0, 0, 10]
。总数为10
。