拔河比赛[CODEVS1959]解题报告

本文主要是介绍拔河比赛[CODEVS1959]解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面：将n个数分成两部分，使其个数之差不超过1，且两部分和之差最小。n<=100,<=450.

思路：由于观察到ai很小，所以很容易就想到的一个思路是以数的大小和个数作二维费用布尔背包，求其当个数为n>>1时最接近的解。

   这是我很早就想到了的，但这道题还是做了很久，因为算下时间复杂度的话可以发现是,这个应该是要挂的。。

  

所以我就想呀想，想呀想。。花了很久很久。。但是实在想不出更好的做法了。。

所以我就对自己说，诶，实在没办法了，就写个超时算法试试吧，万一评测机略牛呢。。

结果我写的时候——突然就发现了！

一个优化：

其实我们循环费用的时候，根本没必要循环到底，只需要循环到和即可，这样的话就可以得到>>2的的时间复杂度了；这样的话，应该是可以卡过的！！

总结：我们在设计算法的时候，当发现设计出了10^8的算法时，不要灰心、不要轻言放弃，要想一想是否常数够小？是否能在常数上做一些优化。轻言放弃是不可取的。

这篇关于拔河比赛[CODEVS1959]解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---