POJ 1011 解题心得

September 08, 2013 17:24


无聊了又去poj解题玩,今天早上9点到下午5点半,折腾了一天终于把poj 1011完成了,提交了几次, 一次16MS,两次32MS,懒的再优化了(能力有限,嘿嘿)

题目链接

早上一早上就是想着怎么解,递归搜索那是肯定要做的,期间思路不清楚, 浪费了几个小时,终于到下午吃完饭后想通了,慢慢实现,不过悲剧的是老是TLE, 计算题目回复里的一个测试数据用了接近4分钟的时间,TLE太严重了

然后把别人的代码看了几次,速度还是没提上来,虽然有点进步,但还是破不了3分钟的坑, 别人代码注释少,真心难读。。。又折腾了一两个小时,终于在结合他人心得与自己的思考下, 完成了一次飞跃式的进步,由三分钟成功跑到3S,提交后成功通过,用时16MS

说题目解法吧,不乱扯了,基本步骤就是:拿到数据先排序,然后开始假设原木棍长度,最好从小到大验证

排序不用说了,我用了C++自带的算法库,假设木棍原来的长度就先到最大的小段开始, 这个就不用解释了吧;然后用总长度mod假设的长度,如果为0的话再去验证是否可以拼接起来( 不为0肯定拼不起的。。)

最浪费时间的就是拼接验证了,拼接思路:

在计算过程中要注意的几点:

然后 原代码 大家可以参考,或是是指点下

Comments: