-1

一个N整数数组被分成两部分K和N-K元素，使得这两部分中元素之和之间的差值最大化。

TEST CASES
N=5, K=2
arr = [8 4 5 2 10]
O/P: 17 because (8+5+10) − (4+2) = 23 − 6 = 17.

N=8, K=3
arr= [1 1 1 1 1 1 1 1]
O/P: 2 because (1+1+1+1+1)-(1+1+1)=2

我要做的是首先对数组中的所有元素求和。然后，找到数组中最小K元素的总和，并从第一个元素中减去后者的两倍。

def smallestKSum(arr,K):
    # returns the sum of the smallest K now. in the array
    arr.sort()
    r=0
    for i in range(K):
        r=r+arr[i]
    return r

N,K = map(int,raw_input().split())
arr = map(int,raw_input().split())
s = sum(arr)
print s-(2*smallestKSum(arr,K))

上述解决方案在上述测试用例上运行良好，但Wrong Solution在我尝试提交时仍然显示。您可以在此链接中查看问题。

有什么我想念的吗？我可以在K不对数组进行排序的情况下找到最小数目的总和吗？

4

2 回答 2

2

您缺少的测试用例是 k 可能大于 nk。

所以将 k 设为 min(nk,k)

你为什么不在同一个函数中找到剩余元素的总和，而不是把所有元素相加，然后再减去。尝试这个：

def smallestKSum(arr,K):
    # returns the sum of the smallest K now. in the array
    arr.sort()
    r=0
    s=0
    for a in arr[:K]: 
       r += a 
    for a in arr[K:]: 
       s += a
    return s-m

返回值是您需要的答案

于 2013-06-30T06:10:38.087 回答
2

有时，孩子应该携带更多的重量以最大化差异。

例如，如果权重是 [1,2,3,4]，k 是 3，kid 应该取 [2,3,4]。

(2+3+4) - (1) = 8

不是，[1,2,3]

(1+2+3) - (4) = 1

def smallestKSum(xs, k):
    xs = sorted(xs)
    return max(
        abs(sum(xs[k:]) - sum(xs[:k])),
        abs(sum(xs[-k:]) - sum(xs[:-k]))
    )
于 2013-06-30T06:42:39.277 回答