-1

整数の配列は、要素Nの 2 つの部分に分割され、これら 2 つの部分の要素の合計の差が最大になるようにします。KN-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後者の 2 倍を最初の要素から引きます。

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

違いを最大化するために、子供はより多くの体重を運ぶ必要がある場合があります。

たとえば、重みが [1,2,3,4]、k が 3 の場合、子供は [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 に答える
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 に答える