# 把最胖的人从一架超载的飞机上抛下。

### 12 Solutions collect form web for “把最胖的人从一架超载的飞机上抛下。”

` `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.` `

` `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()); } } }` `

@Blastfurnace在正确的轨道上。 您使用quickselect枢轴是重量阈值。 每个分区将一组人分成组，并返回每组人的总重量。 你继续打破适当的斗，直到你的水桶相当于最高的重量的人超过3000磅，而你最低的桶是1人（也就是说，它不能再分裂）。

` `#!/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]` `

1. 如果坐在靠窗的座位上的乘客比坐在靠窗的座位上的人重，则要求坐在靠窗的座位上的乘客移动到中间的座位上。

2. 要求中间座位的乘客在靠近过道的位置与乘客交换。

3. 要求左侧过道座位上的乘客与右侧过道座位上的乘客交换重量。

4. 泡沫将乘客分配在右侧过道的座位上。 （n行n步）。 – 要求右边通道的乘客与前面的人交换n次-1。

5把他们踢出门，直到你达到3000磅。

3步+ n步加30步，如果你有一个真正瘦客运负荷。

@James在注释中有答案：一个`std::priority_queue`如果你可以使用任何容器，或者`std::make_heap``std::pop_heap` （和`std::push_heap` ）的组合，如果你想使用类似`std::vector`

` `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)` `

` `weights = [2500] + [1/(2**n+0.0) for n in range(100000)] + [3000]` `

• 是否需要知道T的完整定义的std :: unique_ptr <T>？
• 在C ++中使用指向dynamic分配对象的向量时如何避免内存泄漏？
• Endianness是什么时候成为一个因素？
• std :: string :: c_str（）和临时对象
• 对于STL或！STL，这是个问题
• 通过inheritance扩展C ++标准库？
• 什么是std :: pair？
• 为什么一个C ++向量被称为向量？
• 基于范围的“for”循环是否弃用了许多简单的algorithm？
• 如何在GDB中打印C ++向量的元素？
• STL或Qt容器？