kczno1的博客

博客

2017-07-02 17:08:33 By kczno1

贪心就是从小到大枚举编号，

之后在已经有球的柱子里随便找一个能放的放。

如果找不到，就新开一个柱子。

这个方法能通过本题。

但它是正确的吗？为什么？

(虽然看到网上已经有人问了，但没看到解答)

mcfxmcfx

大概对于n<=55是正确的（滑稽）

r_64

可以证明。用数学归纳法证明贪心法每次的选择是唯一的(即，只能把球放到0或1个已经放了球的柱子上)，且答案为(一个简单式子，暂不剧透)。用dilworth定理可以证明这个是最优的(hint:柱子的顶端构成一个反链)。这个算法work是因为“加起来是平方数”的性质很好。改成其他条件就做不了了。

pengyihao

安利一发自己的博客：[证明](http://blog.csdn.net/xy20130630/article/details/51336960)

RingweEH

<https://loj.ac/d/562>

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。