将最胖的人从超载的飞机上摔下来。
一种方法是使用最小堆（std::priority_queue在C ++中）。假设您有一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多个物品。
最坏的情况是按重量从最低到最大的顺序显示乘客。这将需要将每个乘客添加到堆中，并从堆中删除每个乘客。不过，如果有100万乘客，并且假设最轻的乘客体重为100磅，那么n log k工作量就很小。
如果您随机获得乘客的体重，则性能会更好。我在推荐引擎中使用了类似的内容（我从几百万个列表中选择了前200个项目）。我通常最终只将50,000或70,000个项目实际添加到堆中。
我怀疑您会看到非常相似的东西：您的大多数候选人将被拒绝，因为他们比已有的最轻的人轻。并且Peek是一项O(1)操作。
有关堆选择和快速选择的性能的更多信息，请参阅理论与实践相结合。简短版本：如果您选择的项目少于总项目数的1％，那么堆选择显然是快速选择的赢家。超过1％，然后使用快速选择或类似Introselect的变体。
假设您有一架飞机，而且燃油低。除非飞机掉落3000磅的乘客体重，否则它将无法到达下一个机场。为了最大程度地挽救生命，我们希望首先将最重的人员从飞机上救出。
哦，是的，飞机上有数百万人，我们希望找到一种最佳算法来找到最重的乘客，而不必对整个列表进行排序。
这是我尝试用C ++编写代码的代理问题。我想按重量对旅客舱单进行“ partial_sort”，但我不知道我需要多少个元素。我可以实现自己的“
partial_sort”算法（“ partial_sort_accumulate_until”），但是我想知道是否有使用标准STL进行此操作的简便方法。