运载卡车找不同介绍

之前的问题是固定卡车运载量，求最少的卡车数量。现在问题变为，固定卡车数量的上限，求最小的卡车运载量，两者之间进行了颠倒。这样一来，问题的解法就不是那么显而易见了。换句话说，给定运载量求卡车数量是简单的，但是给定卡车数量求运载量是比较困难的。

现在有n组货物需要通过卡车运送，每组货物的量可以用一个整数ai表示。我们用数组a=[a1,a2,...,an]表示n组货物的量。每量卡车的运载量为一**整数k。运送货物时，如果某一组货的量ai超过了卡车的运载量k，这组货可以被分到多量卡车上进行运送。但是，不同组的货不能混装到同一辆卡车上。换句话说，一辆卡车只能运送一组货的一部分，即使它没有满载也不能同时运送另一组货。问题为：如果想要同时运送所有的n组货物，至少需要多少量卡车？

其它条件不变。现在我们希望所有的货物可以用至多m辆卡车来运送。问：当卡车的运载量最少为多少时可以满足这一要求？保证m>=n（否则一定无解）。

这一二分算法的关键在于第2步中是否能够高效的“验证mid是否满足条件”。幸运的是，这一步可以在O(n)复杂度内完成，因为这就是前边已经讲过的简单版本问题:)。还记得我们之前怎么说的吗？给定运载量求卡车数量是简单的：给定运载量为mid，我们可以轻松的求出至少需要多少量卡车。如果这个数量小于等于m，则mid满足要求，否则不满足要求。

据报道称，运载着炸药的卡车驶过位于俄罗斯和***的交界处的大桥，突然爆炸，而且就在那时一列油罐火车正好驶来，这更是加剧了危害，刹那间火光冲天，与此同时还造成了至少3人身亡。