假设你有一架飞机，但油量很低。为了到达下一个机场，除非卸下 3000 磅的乘客重量，否则该飞机将无法到达。为了拯救尽可能多的生命，我们希望首先把最重的人扔出飞机。
还有，这架飞机上有数百万人，我们需要一个最优算法来找出最重的乘客，而不必对整个名单进行排序。
这是我在尝试使用 C++ 编写代码时遇到的代理问题。我想按重量对乘客名单进行 "partial_sort"，但我不知道需要多少元素。我可以实现自己的 "partial_sort" 算法（"partial_sort_accumulate_until"），但我想知道是否有更简单的方法使用标准 STL 完成此操作。
这对你的代理问题没有帮助，但是：
为了让100万名乘客减轻3000磅的重量，每个乘客必须失去（3000/1000000）= 0.003磅。这可以通过抛弃每个人的衬衫、鞋子，甚至指甲剪来实现，从而拯救每个人。这假设在飞机使用更多燃料之前有效地收集和抛弃所需减轻的重量。
实际上，他们不再允许携带指甲刀，所以这个方法行不通。
一种方法是使用 最小堆（在 C++ 中可使用 std::priority_queue）。以下是使用 MinHeap 类进行操作的示例代码。（是的，我的示例代码是用 C# 写的，但我认为你能明白。）
int targetTotal = 3000;
int totalWeight = 0;
// this creates an empty heap!
var myHeap = new MinHeap<Passenger>(/* need comparer here to order by weight */);
foreach (var pass in passengers)
{
if (totalWeight < targetTotal)
{
// unconditionally add this passenger
myHeap.Add(pass);
totalWeight += pass.Weight;
}
else if (pass.Weight > myHeap.Peek().Weight)
{
// If this passenger is heavier than the lightest
// passenger already on the heap,
// then remove the lightest passenger and add this one
var oldPass = myHeap.RemoveFirst();
totalWeight -= oldPass.Weight;
myHeap.Add(pass);
totalWeight += pass.Weight;
}
}
// At this point, the heaviest people are on the heap,
// but there might be too many of them.
// Remove the lighter people until we have the minimum necessary
while ((totalWeight - myHeap.Peek().Weight) > targetTotal)
{
var oldPass = myHeap.RemoveFirst();
totalWeight -= oldPass.Weight;
}
// The heap now contains the passengers who will be thrown overboard.
n log k 成比例，其中 n 是乘客数量，k 是堆中最大的项目数。如果我们假设乘客的重量通常为100磅或更多，则堆不太可能同时包含超过30个项目。n log k 的计算结果仍然很小。Peek 是一个 O(1) 操作。std::priority_queue。 - bdonlan以下是一个相当简单的实现直截了当的解决方案。 我不认为有一种更快且100％正确的方法。
size_t total = 0;
std::set<passenger> dead;
for ( auto p : passengers ) {
if (dead.empty()) {
dead.insert(p);
total += p.weight;
continue;
}
if (total < threshold || p.weight > dead.begin()->weight)
{
dead.insert(p);
total += p.weight;
while (total > threshold)
{
if (total - dead.begin()->weight < threshold)
break;
total -= dead.begin()->weight;
dead.erase(dead.begin());
}
}
}
该算法通过填充“死亡人员”集合，直到达到阈值。一旦达到阈值，我们继续遍历乘客列表，试图找到比最轻的死亡人员更重的任何人。当我们找到一个时，将其加入列表，然后开始将列表中最轻的人“救出”，直到不能再救出为止。
在最坏情况下，这将执行与整个列表排序大致相同的操作。但在最好情况下（用前X个人适当地填充“死亡名单”），它将执行O(n)的操作。
continue;旁边更新total。总之，这就是我要发布的答案。超级快速解决方案。 - Mooing Duck@Blastfurnace的想法是正确的。您可以使用快速选择算法，其中枢轴是重量阈值。每个分区将一组人拆分为多个集合，并返回每组人的总体重。您继续打破适当的桶，直到最高重量组对应的桶超过3000磅，而该组中最低的桶有1个人（也就是说，无法再进一步拆分了）。
这个算法在平均情况下是线性时间的，但是在最坏情况下是二次的。我认为这是唯一的线性时间算法。
以下是一个Python解决方案，演示了该算法：
#!/usr/bin/env python
import math
import numpy as np
import random
OVERWEIGHT = 3000.0
in_trouble = [math.floor(x * 10) / 10
for x in np.random.standard_gamma(16.0, 100) * 8.0]
dead = []
spared = []
dead_weight = 0.0
while in_trouble:
m = np.median(list(set(random.sample(in_trouble, min(len(in_trouble), 5)))))
print("Partitioning with pivot:", m)
lighter_partition = []
heavier_partition = []
heavier_partition_weight = 0.0
in_trouble_is_indivisible = True
for p in in_trouble:
if p < m:
lighter_partition.append(p)
else:
heavier_partition.append(p)
heavier_partition_weight += p
if p != m:
in_trouble_is_indivisible = False
if heavier_partition_weight + dead_weight >= OVERWEIGHT and not in_trouble_is_indivisible:
spared += lighter_partition
in_trouble = heavier_partition
else:
dead += heavier_partition
dead_weight += heavier_partition_weight
in_trouble = lighter_partition
print("weight of dead people: {}; spared people: {}".format(
dead_weight, sum(spared)))
print("Dead: ", dead)
print("Spared: ", spared)
输出：
Partitioning with pivot: 121.2
Partitioning with pivot: 158.9
Partitioning with pivot: 168.8
Partitioning with pivot: 161.5
Partitioning with pivot: 159.7
Partitioning with pivot: 158.9
weight of dead people: 3051.7; spared people: 9551.7
Dead: [179.1, 182.5, 179.2, 171.6, 169.9, 179.9, 168.8, 172.2, 169.9, 179.6, 164.4, 164.8, 161.5, 163.1, 165.7, 160.9, 159.7, 158.9]
Spared: [82.2, 91.9, 94.7, 116.5, 108.2, 78.9, 83.1, 114.6, 87.7, 103.0, 106.0, 102.3, 104.9, 117.0, 96.7, 109.2, 98.0, 108.4, 99.0, 96.8, 90.7, 79.4, 101.7, 119.3, 87.2, 114.7, 90.0, 84.7, 83.5, 84.7, 111.0, 118.1, 112.1, 92.5, 100.9, 114.1, 114.7, 114.1, 113.7, 99.4, 79.3, 100.1, 82.6, 108.9, 103.5, 89.5, 121.8, 156.1, 121.4, 130.3, 157.4, 138.9, 143.0, 145.1, 125.1, 138.5, 143.8, 146.8, 140.1, 136.9, 123.1, 140.2, 153.6, 138.6, 146.5, 143.6, 130.8, 155.7, 128.9, 143.8, 124.0, 134.0, 145.0, 136.0, 121.2, 133.4, 144.0, 126.3, 127.0, 148.3, 144.9, 128.1]
假设像人的体重一样，你对值的最大和最小值有一个很好的想法，使用基数排序在O(n)的时间内对它们进行排序。然后从列表的最重端向最轻的端逐步处理。总运行时间：O(n)。不幸的是，STL中没有基数排序的实现，但编写它相当简单。
大规模并行锦标赛排序：
假设过道两侧都有三个座位：
如果靠窗的乘客比窗户座位上的人重，就请他们移到中间座位。
如果中间座位上的乘客更重，请让他们和过道座位上的乘客交换位置。
如果右边过道座位上的乘客更重，请让左边过道座位上的乘客换到右边去。
对右边过道座位上的乘客进行气泡排序（对于n排需要n步）。 -- 让右侧过道座位上的乘客与前面的乘客交换n-1次。
5 将乘客踢出飞机门，直到总重量达到3000磅。
3个步骤+ n个步骤，如果乘客负载非常少，则需要额外30个步骤。
对于双过道飞机，指令更加复杂，但性能大致相同。
我会使用std::nth_element函数将20个最重的人在线性时间内分开。然后使用更复杂的方法找到并淘汰其中最重的人。
您可以对列表进行一次遍历，以获取平均值和标准偏差，然后使用它来估计需要前往的人数。使用partial_sort根据该数字生成列表。如果猜测过低，请在剩余部分上再次使用partial_sort并进行新的猜测。