雅文吧言情小说网 > 都市言情 > 重生学神有系统 > 第244章 vigenère密码和国王游戏

一共10个检查点,每个检查点10分。

比赛对于程序运行时间的限制,是每个检查点不超过1秒。

对于运行空间的限制,是每个程序使用的内存,不得超过128兆。

无论在哪个检查点超时或者输出错误,都会扣掉该点的分值。

计算机打分的时候,一般会输入强弱不同的10组测试数据。

遇上小点的数字,比如本题中前20%的数据,只要程序没有逻辑错误,基本都能通过测试,拿到分数。

但当n稍微大一点的时候,使用暴力搜索算法,很可能会超过1s的时限。

所以,一定要找出规律,对输入的n组a、b进行预处理。

江寒在纸面上推演了一下,很快得到了一个猜想:当大臣们按axb的积升序排序时,得到的序列就是最优的方案。

那么原本的暴力搜索程序,就可以改造一下了。

第一步,排序,求出最优方案时的队列,第二步,计算该情况下的m值。

毫无疑问,这个算法的效率远比暴力搜索更高,其运行时间取决于使用的排序算法的时间复杂度。

江寒先编制了一个最朴素的暴力搜索算法,测试了一下,验证程序没有逻辑错误后,另存了一份。

然后又按照改进后的思路,修改了一下代码,用快速排序整理队列,然后计算m值。

接下来就是比较好玩的东西了。

对拍。