GGboy的圣诞袜

目标：使得配对的袜子能量值最小

首先我们先证明，如果第i双袜子没有丢，我们让那双袜子自己配对的操作是最优的。

证明：

如果有四只袜子

++

所以我们不用考虑成双的袜子，只需要考虑丢失了颜色的袜子即可。

因此我们的问题转换为，配对只袜子，使得能量值最小

现在我们来分情况讨论

如果K是偶数，似乎排序，然后每两个袜子进行配对即可。为什么呢？这里设排完序的袜子是A1到AK

用归纳法证明，在最优解中，总是和进行配对

假设和进行配对，和进行配对，且

就有+ +,因为左边的每一项都大于右边的每一项

所以我们选择和去配对，而不是其他。因此偶数的情况，我们就证明了

如果k是奇数，我们可以枚举那只不参与配对的袜子，然后剩下的袜子按照偶数的情形去解决就行。但是暴力枚举是n2复杂度。如果我们可以预先处理一些值呢，比如当我们让是那只不参与配对的袜子，那么其他的和应该是+ 因此我们可以预处理的前缀和以及后缀和，就可以将时间复杂度降低为On了

具体代码实现：

def I(): return input()
def II(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(input().split())
def LII(): return list(map(int, input().split()))

N, k = MI()

arr = LII()
arr.sort()


# 奇数，枚举不参与配对的袜子，只需要枚举1，3，5，7...即可
pre = [0]*(k+1)
suf = [0]*(k+1)
for i in range(1, k+1):
    pre[i] = pre[i-1]
    if i % 2 == 0:
        pre[i] += arr[i-1] - arr[i-2]
for i in range(k-1, -1, -1):
    suf[i] = suf[i+1]
    if ((k-i)%2==0):
        suf[i] += arr[i+1] - arr[i]
ans = float("inf")
for i in range(0, k+1, 2):
    ans = min(ans, pre[i] + suf[i])
print(ans)