卡在写 python 列表缩减程序

Question

我一直在为以下问题编写 python 代码，非常感谢任何人能帮助找到代码中的问题。

列表缩减：

给定一个大小为 N 的整数列表 L 和一个整数 K。您最多可以对列表执行以下操作 k 次：

选择列表中的任意两个元素。
将任何元素乘以 2。
将另一个元素除以 2，如果元素为奇数则取上限。

注意：这样操作后，列表发生了变化，后续操作会使用变化后的列表。

您需要在执行最多 k 个这样的操作后，最小化列表中存在的所有元素的总和。

输入格式：

第一行包含 N K 如上所述。
第二行包含N个space个分隔的整数，表示最初的列表，

输出格式：

在最多执行 k 次操作后，在最后打印列表中所有元素的最小可能总和。

代码：

def solve (X, arr):
    Sum = 0
    largestDivisible, minimum = -1, arr[0]
    for i in range(0,N):
        Sum += arr[i]
        if(arr[i]%X == 0 and largestDivisible < arr[i]):
            largestDivisible = arr[i]
        if arr[i] < minimum:
            minimum = arr[i]
    if largestDivisible == -1:
        return Sum

    sumAfterOperation = (Sum-minimum-largestDivisible+(X*minimum)+(largestDivisible//X))
    return min(Sum,sumAfterOperation)
    

N=5 
X =2
#map(int, input().split())
arr = [10, 7, 4, 2, 1]
#list(map(int, input().split()))

out_ = solve(X, arr)
print (out_)
output: 20

预期输出：19

Answer 1

不是最优程序。

思路：将最小元素相乘除以最大元素得到总和最小的序列。你想要处理负数吗？ K是否取负值？

K = int(input())
arr = list(map(int, input().split()))

for _ in range(K):
    arr.sort()
    arr[0] *= 2
    arr[-1] = arr[-1] // 2 + arr[-1] % 2

print(sum(arr))

更有效的解决方案。

K = int(input())
arr = list(map(int, input().split()))

for _ in range(K):
    mn, mx = min(arr), max(arr)
    mn_i = arr.index(mn)
    if mn != mx:
        mx_i = arr.index(mx)
    else:
        mx_i = arr.index(mx, mn_i+1)
    arr[mn_i] *= 2
    arr[mx_i] = arr[mx_i] // 2 + arr[mx_i] % 2
print(sum(arr))

和算法解决方案。

K = int(input())
arr = list(map(int, input().split()))

for _ in range(K):
    mn, mx = 0, 0
    for i, x in enumerate(arr):
        if x < arr[mn]:
            mn = i
        if x >= arr[mx]:
            mx = i
    arr[mn] *= 2
    arr[mx] = arr[mx] // 2 + arr[mx] % 2

print(sum(arr))

卡在写 python 列表缩减程序

Stuck in writing python list reduction program

python

list

reduction