题解：P11748 「TPOI-1B」ASPAP

· · 题解

贪心好难。。。

看到有大佬 O(n^3) 卡过去了，啧啧称奇

赛时一直在调取第s个排列的做法，没看阳历，导致一分没得

看完题解才发现其实这道题并不能纯粹的贪心，特此记录

思路

一开始很容易想到一种做法：选取第s个排列

但这种做法的错误性在样例中就可以体现

对于样例 1 中 n=4 的排列，1,4,3,2 的结果为 24，而 2,1,3,4 为 21

但这种思路的其中一部分是没有错误的：

"如果前面的若干位已经确定不变，剩下的可以任意改变顺序，那么改变顺序时，让数值较大的放在前面"

有了这个基础，我们就要思考怎么确定不变的若干位

那么手模一下就可以发现

如果填入当前位可填数的次大值及以内的数

就可以使第 i 位后面的位都可以填入剩余数字的任意排列

所以对于当前位就取两种情况：

  1. 求出这一位填入可填数的次大值，后面的每个数将剩余数降序排列后的结果

  2. 后面所有位填剩余数的最大值的最大结果

以上两种情况取最大值输出答案即可