我尝试总结一下问题陈述，大致如下：
给定n、k以及一个数组（列表）arr，其中n = len(arr)，k是集合（1, n]中的整数。
对于一个数组（或列表）myList，不公平度之和定义为myList中所有可能配对（每个组合包含两个元素）之间的绝对差值之和。
为了解释清楚，如果mylist = [1, 2, 5, 5, 6]，那么最小不公平度之和（MUS）是指上述定义下的最小值。请注意，元素按其在列表中的索引而非值来唯一确定。
如果您需要查看问题陈述，请单击此处。 我的目标 给定
您只需要检查
上述代码对于
我在 Stack Overflow 上发布了同样的问题，链接在这里（您可能想要查看以正确理解我的意思 - 它包含讨论和 fusion 的答案，这使我想到了第二种方法 - 更好的方法（我应该说是 fusion 的方法 xD）。）。
第二种方法：
给定n、k以及一个数组（列表）arr，其中n = len(arr)，k是集合（1, n]中的整数。
对于一个数组（或列表）myList，不公平度之和定义为myList中所有可能配对（每个组合包含两个元素）之间的绝对差值之和。
为了解释清楚，如果mylist = [1, 2, 5, 5, 6]，那么最小不公平度之和（MUS）是指上述定义下的最小值。请注意，元素按其在列表中的索引而非值来唯一确定。
MUS = |1-2| + |1-5| + |1-5| + |1-6| + |2-5| + |2-5| + |2-6| + |5-5| + |5-6| + |5-6|
如果您需要查看问题陈述，请单击此处。 我的目标 给定
n, k, arr（如上所述），找到所有可能的子数组的不公平和中的最小不公平和，并约束每个子数组的长度为 k [我相信这是一件好事，可以使我们的生活变得容易 :) ]
我尝试过的方法
嗯，这里还有很多要添加的，所以我会尽量简短。
我的第一种方法 是使用 itertools.combinations 获取所有可能的组合，使用 statistics.variance 检查其 数据分布（是的，我知道我有点乱）。
在查看下面的代码之前，您是否认为这些方差和不公平和是完全相关的（我知道它们强烈相关），即具有最小方差的子数组必须是具有 MUS 的子数组？？您只需要检查
LetMeDoIt（n，k，arr） 函数。如果需要MCVE，请查看下面的第二个代码片段。from itertools import combinations as cmb
from statistics import variance as varn
def LetMeDoIt(n, k, arr):
v = []
s = []
subs = [list(x) for x in list(cmb(arr, k))] # getting all sub arrays from arr in a list
i = 0
for sub in subs:
if i != 0:
var = varn(sub) # the variance thingy
if float(var) < float(min(v)):
v.remove(v[0])
v.append(var)
s.remove(s[0])
s.append(sub)
else:
pass
elif i == 0:
var = varn(sub)
v.append(var)
s.append(sub)
i = 1
final = []
f = list(cmb(s[0], 2)) # getting list of all pairs (after determining sub array with least MUS)
for r in f:
final.append(abs(r[0]-r[1])) # calculating the MUS in my messy way
return sum(final)
上述代码对于
n<30 运行正常，但对于更大的数字会出现 MemoryError 。
在 Python 聊天中，Kevin 建议我尝试使用 generator ，它非常 memory efficient （确实如此），但由于生成器会在我们 迭代它们时即时生成这些组合，因此估计 n=50, k=8 会需要超过 140 小时（:/）。我在 Stack Overflow 上发布了同样的问题，链接在这里（您可能想要查看以正确理解我的意思 - 它包含讨论和 fusion 的答案，这使我想到了第二种方法 - 更好的方法（我应该说是 fusion 的方法 xD）。）。
第二种方法：
from itertools import combinations as cmb
def myvar(arr): # a function to calculate variance
l = len(arr)
m = sum(arr)/l
return sum((i-m)**2 for i in arr)/l
def LetMeDoIt(n, k, arr):
sorted_list = sorted(arr) # i think sorting the array makes it easy to get the sub array with MUS quickly
variance = None
min_variance_sub = None
for i in range(n - k + 1):
sub = sorted_list[i:i+k]
var = myvar(sub)
if variance is None or var<variance:
variance = var
min_variance_sub=sub
final = []
f = list(cmb(min_variance_sub, 2)) # again getting all possible pairs in my messy way
for r in f:
final.append(abs(r[0] - r[1]))
return sum(final)
def MainApp():
n = int(input())
k = int(input())
arr = list(int(input()) for _ in range(n))
result = LetMeDoIt(n, k, arr)
print(result)
if __name__ == '__main__':
MainApp()
这段代码对于 n 小于等于1000的情况（可能更大），是完美的，但是当 n 超过10000时（最大测试用例有 n=100000），由于 超时 而无法继续执行（在线评测限制为5秒 :/）。
=====
你会如何解决这个问题，以满足给定时间限制（5秒）下的所有测试用例？（问题在算法和动态规划中列出）
（您可以参考以下内容：
- 其他候选人的成功提交记录（使用py3、py2、C++、java）- 以便您为我和未来的访问者解释那种方法）
- 问题设置者的一篇文章，解释如何解决该问题
- 问题设置者自己的解决方案代码（使用py2、C++）。
- 输入数据（测试用例）和期望输出
编辑1 ::
对于这个问题的未来访问者，我现在得出的结论是：
即方差和不公平总和并不是完全相关（它们是强烈相关），这意味着在许多整数列表中，具有最小方差的列表不一定总是具有最小不公平总和的列表。如果您想知道原因，我实际上在math stack exchange上单独提出了一个问题HERE，其中一位数学家为我证明了这一点 xD（这值得一看，因为它出人意料）。
至于整个问题，您可以阅读下面archer和Attersson的答案（仍在试图找出一种简单方法来解决此问题 - 目前应该不远了）
感谢您的任何帮助或建议 :)
MUS = |1-2| + |1-5| + |1-5| + |1-6| + |2-5| + |2-5| + |2-6| + |5-5| + |5-5|"你确定这里末尾没有漏掉+ |5-6| + |5-6|吗？ - Stef