1 条题解

  • 0
    @ 2026-11-15 19:21:49

    题目分析

    能够证明逆序对个数不会超过 200200 个。

    f[i][j]f[i][j] 表示长度为 ii 的排列中,逆序对个数为 jj 的排列有多少个,可以利用 DP + 前缀和在 O(200n)O(200n) 的时间复杂度内计算。

    根据 f[i][j]f[i][j] 可以计算出排名第 kk 小的排列有多少个逆序对。

    然后从第一位逐位开始确定,假设已经确定了前 xx 位,我们可以知道前 xx 个数字内部之间的逆序对个数,和前xx 个和后 n−xn-x 个数字之间的逆序对个数,从而推出后 n−xn-x 个数字内部之间的逆序对个数,这个方案数可以利用f[i][j]f[i][j] 快速计算出,时间复杂度为 O(200n)O(200n),如果实现的不精细会退化到 O(n2)O(n^2)。

    • 1

    信息

    ID
    176
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者