我得到了一张a队和B队的表格，其中每对2名球员都有一个数字。行代表A队球员的球员和B队球员的列。如果数字为正，则表示球员A比B队的球员好，反之亦然。
例如：
-710 415 527 -641 175 48
-447 -799 253 626 304 895
509 -523 -758 -678 -689 92
24 -318 -61 -9 174 255
487 408 696 861 -394 -67
两队都知道这张表。现在，所做的是，A队报告5名球员，B队可以查看他们，并为他们选择最好的5名球员。如果我们想对球队进行比赛，我们会将表格中给定位置的数字相加，因为我们知道每支球队都有一名队长，他被计算了两次(就好像一支球队有6名球员，队长在那里两次)，如果总和为正，那么a队更好。
输入是数字a(行/玩家A的数量)和b(列/玩家B的数量)，表格如下：
6
6
-54 -927 428 -510 911 93
-710 415 527 -641 175 48
-447 -799 253 626 304 895
509 -523 -758 -678 -689 92
24 -318 -61 -9 174 255
487 408 696 861 -394 -67
输出应该是1282。
所以，我所做的是，我把数字放入一个矩阵中，像这样：
a, b = int(input()), int(input())
matrix = [list(map(int,input().split())) for _ in range(a)]
我为此使用了MinHeap和MaxHeap。我把行放在MaxHeap中，因为A队想要最大的，然后我从中得到5个最好的A球员，如下所示：
for player, values in enumerate(matrix):
maxheap.enqueue(sum(values), player)
playersA = []
overallA = 0
for i in range(5):
ov, pl = maxheap.remove_max()
if i == 0: # it is a captain
playersA.append(pl)
overallA += ov
playersA.append(pl)
overallA += ov
了解A球员的B队使用MinHeap找到最好的5名球员：
for i in range(b):
player = []
ov = 0
for j in range(a): #take out a column of a matrix
player.append(matrix[j][i])
for rival in playersA: #counting only players already chosen by A
ov += player[rival]
minheap.enqueue(ov,i)
playersB = []
overallB = 0
for i in range(5):
ov, pl = minheap.remove_min()
if i == 0:
playersB.append(pl)
overallB += ov
playersB.append(pl)
overallB += ov
有了玩家，然后我从矩阵中计算总和：
out = 0
for a in playersA:
for b in playersB:
out += matrix[a][b]
print(out)
然而，这种解决方案并不总是给出正确的解决方案。例如，对于输入：
10
10
-802 -781 826 997 -403 243 -533 -694 195 182
103 182 -14 130 953 -900 43 334 -724 716
-350 506 184 691 -785 742 -303 -682 186 -520
25 -815 475 -407 -78 509 -512 714 898 243
758 -743 -504 -160 855 -792 -177 747 188 -190
333 -439 529 795 -500 112 625 -2 -994 282
824 498 -899 158 453 644 117 598 432 310
-799 594 933 -15 47 -687 68 480 -933 -631
741 400 979 -52 -78 -744 -573 -170 882 -610
-376 -928 -324 658 -538 811 -724 848 344 -308
但没有
11
11
279 475 -894 -641 -716 687 253 -451 580 -727 -509
880 -778 -867 -527 816 -458 -136 -517 217 58 740
360 -841 492 -3 940 754 -584 715 -389 438 -887
-739 664 972 838 -974 -802 799 258 628 3 815
952 -404 -273 -323 -948 674 687 233 62 -339 352
285 -535 -812 -452 -335 -452 -799 -902 691 195 -837
-78 56 459 -178 631 -348 481 608 -131 -575 732
-212 -826 -547 440 -399 -994 486 -382 -509 483 -786
-94 -983 785 -8 445 -462 -138 804 749 890 -890
-184 872 -341 776 447 -573 405 462 -76 -69 906
-617 704 292 287 464 -711 354 428 444 -42 45
所以问题是：它可以这样做吗？或者是否有另一种快速算法(O(n**2)/O(n**3)等)，或者我只是尝试在O(n！)时间复杂性中使用蛮力进行所有可能的组合？
有一种方法可以通过多项式复杂度来实现这一点
为了说明为什么您的解决方案不起作用，让我们考虑另一个更简单的问题。假设每支球队只选择2名球员，没有队长。
让我们也取一个简单的分数矩阵：
1 1 1 2 1
1 1 1 1
0 3 0 2 0
0 0 0 4
00 0 4
在这里你可以看到，A队没有获胜的机会(因为没有负数)，但他们仍然会尽力。他们应该选谁？
使用你的算法，A队应该选出他们最好的球员，他们的排名是：
pa0<pa1＝pa2<pa3=pa4
如果他们选择pa3和pa4，他们都有4分(这很糟糕，但没有pa0的6分那么糟糕)，B队将以8分的优势获胜(他们将选择pb4和其他无关紧要的球员)。
另一方面，如果A队选择了pa0和pa1(根据你的衡量标准，他们比pa3和pa4差)，B队能得到的最好成绩是以5获胜(如果他们选择pb3和任何其他球员)
基本上，你的近似没有考虑到B队只能选择两名球员，因此不能利用pa0+pa1的弱点，而可以很容易地利用pa3+pa4的弱点。
一个更好的解决方案是，A队只考虑每个球员的2个最差分数(如果选择5名球员，则为5分)来评估他们的分数：这将使排名如下：
pa2<pa3＝pa4<pa0<pa1
尽管如此，这仍然是一个近似值：像pa2+pa3这样的一些组合实际上并没有听起来那么糟糕，因为弱点再次扩散到B队无法充分利用它们(尽管在这个例子中，近似值产生了最好的结果)。
我们真正需要挑选的不是两个最好的球员，而是两个球员的最佳组合，遗憾的是，我知道除了尝试所有的美元之外，没有其他办法/(k！(s-k)！)$s中k个球员的组合(球队的规模)。不过，这并没有那么糟糕，对于k=2，这只是$s*(s-1)/2$，对于k=5，这是$s*，尽管在O(s^5)中，其复杂性仍然是多项式。在组合中添加队长只会使组合的数量乘以k。这也需要改变如何计算分数，但你应该能够找到。
既然A队已经选择了他们的球员，B队就可以很容易地选择他们的球员了。这要简单得多，因为在这里每个玩家都可以单独选择。
最后一个算法应如何与开头提供的分数矩阵一起工作的示例。
A队有10种可能的组合：pa0+pa1，pa0+pa2，pa0+pa3，pa0+pa4，pa1+pa2，pa1+pa3，pa1+pa4，pa2+pa3，pa2+pa4，pa3+pa4。他们的得分分别为：5、8、7、7、6、6、7、8。
最好的组合是pa0+pa1，所以这就是他们送给B队的。
B队计算每个球员对pa0+pa1的得分：pb0:2、pb1:2、pb2:2、pb3:3、pb4:2。pb3是最好的，所有其他人都是平等的，因此团队B发送pb3+pb4(例如)，并且；回答"；是5。