UOJ Logo kczno1的博客

博客

求问 「网络流 24 题」魔术球 贪心的正确性?

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

题目:https://loj.ac/problem/6003

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

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

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

这个方法能通过本题。

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

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

评论

mcfxmcfx
大概对于n<=55是正确的(滑稽)
r_64
可以证明。用数学归纳法证明贪心法每次的选择是唯一的(即,只能把球放到0或1个已经放了球的柱子上),且答案为(一个简单式子,暂不剧透)。用dilworth定理可以证明这个是最优的(hint:柱子的顶端构成一个反链)。 这个算法work是因为“加起来是平方数”的性质很好。改成其他条件就做不了了。
pengyihao
安利一发自己的博客:[证明](http://blog.csdn.net/xy20130630/article/details/51336960)

发表评论

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