一共10个检查点,每个检查点10分。
比赛对于程序运行时间的限制,是每个检查点不超过1秒。
对于运行空间的限制,是每个程序使用的内存,不得超过128兆。
无论在哪个检查点超时或者输出错误,都会扣掉该点的分值。
计算机打分的时候,一般会输入强弱不同的10组测试数据。
遇上小点的数字,比如本题中前20%的数据,只要程序没有逻辑错误,基本都能通过测试,拿到分数。
但当n稍微大一点的时候,使用暴力搜索算法,很可能会超过1s的时限。
所以,一定要找出规律,对输入的n组a、b进行预处理。
江寒在纸面上推演了一下,很快得到了一个猜想:当大臣们按axb的积升序排序时,得到的序列就是最优的方案。
那么原本的暴力搜索程序,就可以改造一下了。
第一步,排序,求出最优方案时的队列,第二步,计算该情况下的m值。
毫无疑问,这个算法的效率远比暴力搜索更高,其运行时间取决于使用的排序算法的时间复杂度。
江寒先编制了一个最朴素的暴力搜索算法,测试了一下,验证程序没有逻辑错误后,另存了一份。
然后又按照改进后的思路,修改了一下代码,用快速排序整理队列,然后计算m值。
接下来就是比较好玩的东西了。
对拍。