如何最大限度地减少4个不同学科的分数总和

在游泳比赛中，有4种不同的笔画。每位参赛者都参与其中，并记录完成时间。从所有参赛选手中选出四名选手，这样他们的组合时间最短（一名选手只能选一名）。不止一个这样的团队是可能的，并且所有这样的团队都必须打印输出。如何最大限度地减少4个不同学科的分数总和

例如，假设有四个选手A，B，C和D.它们完成的时间是

A 50.5 52.9 51.8 52.7 
B 50.7 52.7 51.4 52.7 
C 50.7 52.7 51.4 52.8 
D 50.8 52.9 51.6 52.6

这里，最小时间将是（A - 50.5，C - 52.7，B - 51.4 ，D - 52.6）和（A - 50.5，B - 52.7，C - 51.4，D - 52.6）。

我没有任何测试用例。我可以用蛮力来做，但这需要O（n^4）。什么是更好的方法？

2016-11-11 d1729

“以下”对于标题来说确实是一个不好的选择。 – trincot

如果我正确理解问题，请将数据从行转换为列，然后在列之间选择最小值。这将需要O（n日志n） – AndyG

听起来像一个家庭作业问题....你有什么尝试，或者你有几个不同的想法，你已经尝试过？ – random

无论我们想如何分配其他三个笔画，在一次笔画中获得第五或更糟的最佳时间都是毫无意义的：前四笔之一是可用的。在每个笔画中选出前四名候选人，然后过滤4*4*4*4 = 256的可能性以确保作业是唯一的。

O（n）（假设比赛的数量是恒定的）。

由于您需要所有的解决方案，因此无法获得O（n）时间解决方案，因为其中可能存在指数级的许多解决方案。但是，您可以使用上述算法高效地枚举它们。在你的蛮力算法中，插入一个使用上述逻辑的测试来确定是否考虑部分分配可以扩展到最佳解决方案。运行时间为O（n + s），其中s是最优解的数量。

2016-11-11 15:09:51

如果n个候选人在所有比赛中都有相同的时间，那么不会有n！团队？如何计算O（n）或O（nlogn）？ – d1729

@ d1729然后你使用上面的逻辑修剪蛮力。 –

回答