[中文翻译] 到底什么是排序？

Yansuan_HCl · 2024-12-20 21:23:13 · 题解

翻译自 https://www.luogu.com.cn/article/qjugwvvo。

这个的好处就在于，如果 b_i 的取值为 [1,K]，那么甚至不需要排序。唯一需要排序的一次是在 pos 的时候，因为要保证 c'_{b_{pos}} < N。

实际上贪心算法对于每个 i 发生的过程是：

• 将 c'_{b_i} \gets c'_{b_i}+1；
• 将 c 从小到大排序。

由于 b_i \in [1,K]，所以实际上是任选一个 c'_{x}, x \in [1,K] 加 1，都能对应一个 b_i。此时应将 c'_x 设为互相区分的，因为对应的 b_i 不同。此时，排序相当于一个映射，将当前的标号 b_i 双射到原始互不相同的每个 c' 元素，这样就可以最后再排序。

于是要计数的过程是：任选一个 c'_x 加 1，求排完序后是 \{c\}_{pos} 的方案数。