第246章 Vigenère密码和国王游戏

取整。

问题是，如何调整大臣的顺序，才能让获得的金币最多的那个人，得到的金币尽可能的少。

注意，国王始终站在队伍最前方。

然后在输入数据说明中，有如下提示。

对于20%的数据，有1≤n≤10，0

对于40%的数据，有1≤n≤20，0

对于60%的数据，有1≤n≤100；且答案不超过10^9；

对于100%的数据，有1≤n≤1，000，0

这道题的难度比第一题稍有提高，但也不算特别费劲。

此题的坑点在于，输入的数据有可能很大，使用通常的编程方式，只能通过前40%的数据校验，想得高分，就必须使用高精度编程。

解题思路就是穷举法。

针对给出的大臣数N，以及给出的N+1组左右手数字a、b，计算每种可能的站位情况所对应的金币最大值m，再求出集合M={m1，m2，m3，……mk}中的最小值。

由于N个大臣共有N！种站位，所以一旦N足够大，计算量将是非常恐怖的。

这道题一共10个检查点，每个检查点10分。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

对拍。