昨天看到一个很有趣的面试题：

1
2
3
你是山西的一个煤老板，你在矿区开采了有 3000 吨煤需要运送到市场上去卖，从你的矿区到市场有 1000 公里；
你手里有一列烧煤的火车，这个火车最多只能装 1000 吨煤，且其能耗比较大——每一公里需要耗一吨煤；
请问，作为一个懂编程的煤老板的你，你会怎么运送才能运最多的煤到集市？

我很笨，大概花了 20 分钟才得到正确的答案，从一开始思路很模糊，到逐渐清晰，整个过程非常有趣，故记之；

0x1. 这不可能

总共 1000 公里，火车只能装 1000 吨煤，每公里消耗 1 吨煤，到达目的地时，装的都被消耗了，怎么运 ？

0x2. 再思考一下

1000 吨煤跑 1000 公里肯定没法运 (火车都回不来)，如果跑 500 公里呢 ？

  1. 跑 500 公里停下，消耗 500 吨，余 500 吨
  2. 火车返回，也是 500 公里，消耗 500 吨，余 0

来回 1000 公里，消耗 1000 吨，也是白跑；继续缩短距离，250 公里呢？

0x3. 套个数据

路程：0 - 250，煤：3000

第一次：

  1. 跑 250 公里停下，消耗 250 吨，余 750 吨
  2. 卸下 500 吨煤
  3. 火车返回，消耗 250

第二次：继续运剩下的 2000 吨

  1. 跑 250 公里停下，消耗 250 吨，余 750 吨
  2. 卸下 500 吨
  3. 火星返回，消耗 250

第三次：继续运剩下的 1000 吨

  1. 跑 250 公里，消耗 250 吨，余 750 吨
  2. 卸下 750 吨；（不需要返回）

总计：

火车将煤运到 250 公里处，消耗 250 * 5 = 1250 吨，余 1750 吨

路程：250 - 500， 煤 1750

第一次：

  1. 跑 250 公里停下，消耗 250，余 750
  2. 卸下 500 吨煤
  3. 火车返回，消耗 250 吨

第二次：继续运剩下的 750 吨煤

  1. 跑 250 公里停下，消耗 250，卸下 500

总计：

运到 500 公里处，消耗 250 * 3 = 750， 余 1000

路程：500 - 1000， 煤 1000

第一次：

  1. 打到终点，消耗 500， 余 500

最终得到一个答案 500 吨，500 吨是最优的答案吗？

0x4. 总结规律

想要最优解，就得想办法减少运输的损耗，先总结一下 分段跑 250 公里的消耗情况：

  1. 0 - 250

    运 3 次，消耗 250 * 5 = 1250

  2. 250 - 500

    运 2 次，消耗 250 * 3 = 750

  3. 500 - 1000

    运 1 次，消耗 500 * 1 = 500

  4. 剩余

    3000 - 2500 = 500

运 200 公里呢 ？

  1. 0 - 200

    运 3 次, 消耗 200 * 5 = 1000

  2. 200 - 400，余 2000

    运 2 次，消耗 200 * 3 = 600

  3. 400 - 600， 余 1400

    运 2 次，消耗 200 * 3 = 600

  4. 600 - 1000，800

    运 1 次，消耗 400

  5. 剩余

    3000 - 2600 = 400

综上可以得出：

  1. 消耗和运输的次数有关
  2. 运 1 次的消耗是没办法再减少的，需要减少运 3 次 和 运 2 次的消耗
  3. 减少运 3 次 和 运 2 次的消耗，就要避免非满载的情况，例如 分段 200 公里中，路程 400 - 600；

进一步：

  1. 什么时候才会运 3 次 以及 运 2 次呢 ？

    运 3 次 ，煤的数量大于 2000 吨，最大可消耗煤 1000 吨

    运 2 次，煤的数量大于 1000 吨，最大可消耗煤 1000 吨

  2. 运 3 次，运 2 次 如何避免非满载，也就是消耗最小？

    运 3 次，运 2 次的情况下跑最远的距离；

    1. 运 3 次来回总计 5 次，最大可消耗煤 1000 吨，跑的最远距离：

      1000 \ 5 = 200

    2. 运 2 次来回总计 3 次，最大可消耗煤 1000 吨，跑的最远距离：

      1000 \ 3 = 333.33

    3. 跑的最远距离为：533.33，也就是运到的煤的吨数

至此得到了最优的答案：533.33