题解：P3672 小清新签到题

· · 题解

P3672 小清新签到题 题解

  1. 题意
    求 1∼n 的排列，满足逆序对总数为 x，且是所有合法排列中字典序第 k 小的那个。
  2. 思路
    逐位从左到右构造答案：
    • 按从小到大枚举可用数字，保证字典序；
    • 假设当前位选某个数，算出它会新增的逆序对；
    • 判断剩余数字能否凑出还需要的逆序对（一组数字倒序时逆序对最多，只要需求在范围内就可行）；
    • 若当前数字对应的合法排列数小于 k，就减去该数量并跳过；否则确定当前位选这个数，更新状态继续处理下一位。

这里不放代码了，完结撒花~⭐