algorithm - Codejam 2015 资格赛 : Infinite House of Pancakes

Question

问题描述及解决方法after contest analysis

有一种情况我想不通:如果有一个盘子，9个煎饼，那就是测试用例

1
9

“正确答案”是 5

但是怎么办？这是我的“错误”想法:

9 -> {4, 5} -> {4,3,2} -> {3,2,2,2}

所以总共 3 + 3 = 6 分钟，而不是 5

有什么明显的我误解了吗？

Answer 1

我在比赛中也失败了，因为我认为最好的方法是将东西分成两半(以获得最大可能的高度降低)。

但是，在查看您的问题时，我可以看到一种比减半效果更好的方法:

9 -> {6, 3} -> {3, 3, 3}

两次交换加三分钟吃饭:5分钟