把最胖的人从一架超载的飞机上抛下。
假设你有一架飞机，而且燃油很低。 除非飞机降低了3000磅的乘客重量，否则将无法到达下一个机场。 为了节省最多的生命，我们首先要把最重的人从飞机上抛下。
噢，飞机上有数百万人，我们希望有一个最佳的algorithm来find最重的乘客，而不必对整个列表进行sorting。
这是我试图用C ++编码的代理问题。 我想按重量对乘客舱单做一个“partial_sort”，但是我不知道我需要多less元素。 我可以实现我自己的“partial_sort”algorithm（“partial_sort_accumulate_until”），但我想知道是否有更简单的方法来使用标准的STL来做到这一点。
一种方法是使用最小堆 （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个物品。
最糟糕的情况是，如果乘客按照从最低重量到最高重量的顺序排列。 这就要求每一个乘客都要join堆中，每个乘客都要从堆中取出。 尽pipe如此，拥有一百万乘客，并假设最轻的重量为100磅，但是这个数量还是相当小的。
如果随机获得乘客的体重，性能会更好。 我用推荐引擎（我从几百万列表中select前200个项目）的东西。 通常情况下，实际上只有50,000或70,000个物品添加到堆中。
我怀疑你会看到一些非常相似的东西：大多数候选人会被拒绝，因为他们比已经在堆上的最轻的人轻。 Peek是O(1)操作。
有关堆select和快速select的更多信息，请参阅理论遇到实践时 。 简短版本：如果您select的项目总数less于1％，那么堆select明显胜过快速select。 超过1％，然后使用快速select或类似Introselect的变体。
但是这对于您的代理问题将无济于事。
为了让1,000,000名乘客降低3000磅的重量，每名乘客必须损失（3000/1000000）= 0.003磅/人。 这可以通过抛弃每一件衬衫或鞋子，甚至可能是指甲剪报来实现，从而挽救所有人。 这假设有效的收集和抛弃之前需要增加的重量损失，因为飞机使用更多的燃料。
事实上，他们不允许在船上的指甲刀，所以已经出来了。
下面是简单的解决scheme的一个相当简单的实现。 我不认为有一个更快的方法是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()); } } }
这是通过填补一套“死人”，直到达到门槛。 一旦达到这个门槛，我们就会继续浏览那些试图find比最轻的死者更重的乘客名单。 当我们find一个，我们将它们添加到列表中，然后开始“拯救”最轻的人，直到我们不能再保存。
在最糟糕的情况下，这将执行大致相同的整个列表。 但在最好的情况下（“死亡名单”用第一个X人正确填写），它将执行O(n) 。
假设所有乘客都会合作：使用并行分拣networking 。 （也见这个 ）
这是一个现场演示
更新： 替代video （跳转到1:00）
要求一对人进行比较交换 – 你不能比这更快。
@Blastfurnace在正确的轨道上。 您使用quickselect枢轴是重量阈值。 每个分区将一组人分成组，并返回每组人的总重量。 你继续打破适当的斗，直到你的水桶相当于最高的重量的人超过3000磅，而你最低的桶是1人（也就是说，它不能再分裂）。
这个algorithm是线性时间分摊的，但是是二次最坏的情况。 我认为这是唯一的线性时间algorithm 。
下面是一个说明这个algorithm的Python解决scheme：
#!/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]
假设像人们的权重一样，你可以很好地理解最大值和最小值可能是用什么样的基数sorting在O（n）中sorting的。 然后简单地从列表最重的一端向最轻的那一端工作。 总运行时间：O（n）。 不幸的是，在STL中没有实现一个基数sorting，但是写起来非常简单。
为什么不使用具有不同于“sorting”的中止规则的部分快速sorting。 你可以运行它，然后使用更高的一半，继续下去，直到在这个更高的一半内的重量不包含至less要被抛出的重量，比你在recursion中返回一步并对列表进行sorting。 之后，您可以开始从sorting列表的高端抛出人员。
大型平行锦标赛sorting： –
假设一个标准的三个座位的每一边： –
-
如果坐在靠窗的座位上的乘客比坐在靠窗的座位上的人重，则要求坐在靠窗的座位上的乘客移动到中间的座位上。
-
要求中间座位的乘客在靠近过道的位置与乘客交换。
-
要求左侧过道座位上的乘客与右侧过道座位上的乘客交换重量。
-
泡沫将乘客分配在右侧过道的座位上。 （n行n步）。 – 要求右边通道的乘客与前面的人交换n次-1。
5把他们踢出门，直到你达到3000磅。
3步+ n步加30步，如果你有一个真正瘦客运负荷。
对于两个过道的飞机 – 说明比较复杂，但性能差不多。
我可能会使用std::nth_element在线性时间内分割出20个最重的人。 然后用一个更复杂的方法find最重的重物。
你可以通过列表中的一个来获得均值和标准差，然后用它来近似需要去的人数。 使用partial_sort生成基于该号码的列表。 如果猜测较低，则用新的猜测再次使用partial_sort。
@James在注释中有答案：一个std::priority_queue如果你可以使用任何容器，或者std::make_heap和std::pop_heap （和std::push_heap ）的组合，如果你想使用类似std::vector 。
这是一个使用Python内buildheapq模块的基于堆的解决scheme。 它是用Python编写的，所以不能回答原来的问题，但比其他Python解决scheme更清晰（恕我直言）。
import itertools, heapq # Test data from collections import namedtuple Passenger = namedtuple("Passenger", "name seat weight") passengers = [Passenger(*p) for p in ( ("Alpha", "1A", 200), ("Bravo", "2B", 800), ("Charlie", "3C", 400), ("Delta", "4A", 300), ("Echo", "5B", 100), ("Foxtrot", "6F", 100), ("Golf", "7E", 200), ("Hotel", "8D", 250), ("India", "8D", 250), ("Juliet", "9D", 450), ("Kilo", "10D", 125), ("Lima", "11E", 110), )] # Find the heaviest passengers, so long as their # total weight does not exceeed 3000 to_toss = [] total_weight = 0.0 for passenger in passengers: weight = passenger.weight total_weight += weight heapq.heappush(to_toss, (weight, passenger)) while total_weight - to_toss[0][0] >= 3000: weight, repreived_passenger = heapq.heappop(to_toss) total_weight -= weight if total_weight < 3000: # Not enough people! raise Exception("We're all going to die!") # List the ones to toss. (Order doesn't matter.) print "We can get rid of", total_weight, "pounds" for weight, passenger in to_toss: print "Toss {p.name!r} in seat {p.seat} (weighs {p.weight} pounds)".format(p=passenger)
如果k =折腾的乘客数量，N =乘客人数，则该algorithm的最佳情况是O（N），该algorithm的最坏情况是Nlog（N）。 如果k长时间接近N，则会发生最坏的情况。 这是一个最糟糕演员的例子：
weights = [2500] + [1/(2**n+0.0) for n in range(100000)] + [3000]
然而，在这种情况下（把人们从飞机上扔下去（我猜想有降落伞）），那么k必须小于3000，这就是“数百万人”。 因此，平均运行时间应该大约为Nlog（k），这与人数是线性的。
