信息
- ID
- 176
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
能够证明逆序对个数不会超过 200 个。
f[i][j] 表示长度为 i 的排列中,逆序对个数为 j 的排列有多少个,可以利用 DP + 前缀和在 O(200n) 的时间复杂度内计算。
根据 f[i][j] 可以计算出排名第 k 小的排列有多少个逆序对。
然后从第一位逐位开始确定,假设已经确定了前 x 位,我们可以知道前 x 个数字内部之间的逆序对个数,和前x 个和后 n−x 个数字之间的逆序对个数,从而推出后 n−x 个数字内部之间的逆序对个数,这个方案数可以利用f[i][j] 快速计算出,时间复杂度为 O(200n),如果实现的不精细会退化到 O(n2)。