[SHOI2012] 排序

0
15011418730 LV 7 @ 2025-8-24 21:53:12
自动搬运

查看原文

来自洛谷，原作者为

gudzpoz
**

搬运于2025-08-24 21:53:12，当前版本为作者最后更新于2022-06-08 19:25:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本文以 CC BY-SA 4.0 发布。

题意简述
1. 对每一个 $\{x_n\}$ 排列，我们把序列转化为 $x_{a_1}, x_{a_2}, \dots, x_{a_n}$ 的 $\{x_{a_n}\}$ 的中间序列，记作 $\{z_n\}$ 。
2. 对中间序列 $\{x_{a_n}\}$ ，我们按由 $\{a_n\}$ 规定的字典顺序进行比较。
由环构造 $\{a_n\}$

对于一个 $\{x_n\}$ 排列，它一定可以唯一分成多个这样的环状序列：
$$x_{i_1} = i_2, x_{i_2} = i_3, \dots, x_{i_m} = i_1 $$
例如：

$(1, 2, 3)$ ：

$(4, 3, 2, 1)$ ：
我们下面举例说明在我们想要构造的 $\{a_n\}$ 中， $\{x_n\}$ 中的环状结构某种程度上得到了保留。

$\{a_n\}$ 中环状结构体现在最终排序上

对例如 $\dots \rightarrow x_{i_k} \rightarrow x_{i_{k+1}} \rightarrow \dots$ 这样一个环的一部分，假设我们的 $\{a_n\}$ 如下：（顺序不影响）
$\dots, x_{i_k},\dots, x_{i_{k+1}}, \dots$
则经转化后 $\{z_n\}$ 变为：
$\dots, x_{i_{k+1}},\dots, \dots, \dots$
也就是说，其中环里相邻的两个元素 $x_{i_k}, x_{i_{k+1}}$ 在放到 $\{a_n\}$ 序列中后：
- 前者 $x_{i_k}$ 所在位置控制 $\{z_n\}$ 的对应元素的所在位置。
- 后者 $x_{i_{k+1}}$ 所在位置控制前面对应元素的字典顺序（字典指 $\{a_n\}$ ）。
- 最终结果与元素的数值无关（也就是环元素可以任意旋转）。
同时，因为 $x_{i_{k+1}}, x_{i_{k+2}}$ 也是如此。环里的一个元素同时控制后一对的所在位置以及前一对的字典顺序，所以想要使结果最优，我们必须以环作为优化的最小基元。

在下面一节里我们引入一些辅助图像来反映这种环状结构。

尽可能早地生成

要让序列尽可能早地生成，我们从 $a_1$ 看起。

如果 $\{x_n\}$ 里存在一元环 $x_i = i$ 的话，明显 $a_1 = i$ 时可以使得 $\{z_n\}$ 的第一个元素的字典序最小：
我们后续用这样的记号来表示 $\{a_n\}$ 的构造方式。箭头起始位置表示 $\{z_n\}$ 的对应元素的所在位置，箭头末端表示对应元素的字典顺序（也就是箭头上标的数字）。

对于最小化而言，我们希望箭头指向越前越好；

对于最大化而言，我们希望箭头指向越后越好。

请把虚线当作省略号。有时为了避免作图软件排版错乱，我会用圆圈表示本质上同样的节点。
当没有一元环时，例如一个三元环，退而求其次：

因为要最小化字典序，除了首尾，环相邻元素在 $\{a_n\}$ 中也必须相邻（也即箭头指向越前越好），所以我们可以一个一个环地生成 $\{a_n\}$ 的元素。

综上，要生成使最终最小的 $\{a_n\}$ ，则：
1. 所有一元环都应位于 $\{a_n\}$ 最前面；
2. 后面的环应按元素个数由小到大排列；
3. 对每一个环，其元素在 $\{a_n\}$ 中按顺序紧密排布。
例子：

含两个一元环，二元环、三元环各一个的 $\{x_n\}$ ，令其最小的 $\{a_n\}$ 必然是下面这样的：

当然， $\{a_n\}$ 会有很多种，我们只需要将每个环按其最小元素的大小排序，再旋转环使最小元素位于第一个位置，即可得出题目中的“字典序最小的 $\{a_n\}$ ”。这里就不陈列代码了。

如果在查找所有的环的时候注意一下的话，其实很容易直接得出按元素个数、最小元素分别排好序的环，不需要排序和旋转。

思路可以是使用 map<int, vector<int>> 储存环，每个环用一个 int 储存其最小元素（因为知道一个元素即可遍历环）， map 的键为元素个数，vector<int> 按最小元素排序。

下面代码所用到的 map<int, vector<int>>& rings 均要求符合上面条件。

尽可能晚地生成

单个环情况

考虑只有一个很大的环的 $\{x_n\}$ 。因为字典序是贪心的，我们优先考虑前半部分的元素让它们对应箭头指向最后。

例子：奇数元环

例如一个九元环，其对应尽可能晚地生成的 $\{a_n\}$ 必然会将环排列成下面的样子：

这里，我们需要最优先配对的（图中 9, 8, 7, 6）共 $\dfrac{9 - 1}{2} = 4$ 对。

我们把剩下的箭头补完，加箭头时优先让更前面的元素的箭头指向更后面。（注意最终连起来必须只存在一个环。）最终字典序为 987643215：

例子：八元环

同样一个八元环。我们需要最优先配对的（图中 8, 7, 6, 5）共 $\dfrac{8}{2} = 4$ 对。

其对应尽可能晚地生成的 $\{a_n\}$ 必然会将环排列成下面的样子，字典序为 87653214：

多个环

现在设我们有 $n_j$ 个环，对于第 $j$ 个环，令 $c_j$ 为环的元素个数，记：
$$L(j) = \begin{cases} n & c_j = 2 n + 1, \\ n & c_j = 2 n. \end{cases} $$
其中 $L(j)$ 表示这个环里我们需要最优先配对的元素对数。

所以，记奇数环个数为 $m$ ，我们可以确保 $\{a_n\}$ 的结构至少如下：

图中的箭头共 $\sum L = \sum_{j} L(j)$ 个，标为 $\text{s}(i)$ 的元素共 $m$ 个。我们接下来要把其余的箭头连上而已。

前 $\sum L$ 个元素已经连上了最优的箭头，现在看 $\text{s}(1)$ 。

$\text{s}(i)$ 中 $\text{s}$ 表 singular。

下面的图均没有画出两端剩余的元素。
- 如果 $\text{s}(1)$ 其实是个单元环，那么它只能连自己；
- 如果奇数环中存在其它元素，那么我们希望 $\text{s}(1)$ 连接前面的最接近的一个元素（后面都没法连）。
接下来一路连接：

等到 $\text{s}(m)$ 都连好后，最理想的情况是：

从这里可以看出， $\text{s}(i)$ 应该按照环的大小由小到大排序：
- 单元环当然应该最优先。
- 如果是图中的三元环，图中的 1 节点可以指向 s(1)；而如果是更大的环，那么 1 的箭头就要指得更前。
- 更多元环同理，更少元环可以让 s(i) 被更早指到。
偶数部分的排序也可以用相似方法看出。再后续的连线就和单环的方式一模一样了，此处不赘述。

写成代码

使顺序排最后的思路比起排最前的思路复杂一些，代码也麻烦一些。

填充奇数元环
```
/**
 * @param x 输入，注意下面所有元素均以 0 开始，也就是 [3, 1, 2] 的输入已经转为了 [2, 0, 1]。
 * @param rings 环，一个环由其最小元素表示，键为元素个数，值为所有的环（按最小元素从小到大的顺序）。
 * @param a 输出，还是以 0 开始。
 * @param pairs 上面的 L(1) + L(2) + ... + L(n_j)。
 * @param odds 奇数环个数。
 */
void fillOdds(const vector<int>& x, const map<int, vector<int>>& rings,
              vector<int>& a, int pairs, int odds) {
  if (rings.size() == 0) {
    return;
  }
  
  // 缓存，分配的数量比较随意。
  // 例如 `s(i)` 连到前面一个元素后，后面的元素就不能再连到同一个元素了。
  // 下面的算法先遍历 `s(1)` 对应的环，这个时候我们要为后面的 `s(2), ...` 保留连接的空间，
  // 因此我们用 increments 来保留空间。
  // 到 `s(2)` 时，我们需要跳过 `s(1)` 连接过的元素，因此我们用了 used。
  // 当然，可能有更优雅的做法。
  vector<int> increments(rings.rbegin()->first / 2 + 1, 0);
  vector<int> used(rings.rbegin()->first / 2 + 1, 0);
  increments[0] = odds;
  
  // 处理过的环的个数，用来寻找对应的 `s(i)`（`i` 即 `count`）。
  int count = 0;
  
  // 从元素个数从小到大。
  for (auto i = rings.begin(); i != rings.end(); ++i) {
    if (i->first % 2 == 1) {
      auto &someRings = i->second;
      if (i->first != 1) {
        // > 如果有多种生成器能达到要求，那么请输出字典序最小的符合要求的生成器。
        // 单元环与多元环的字典序处理有些许差别。
        fillOdd(x, a, someRings.rbegin(), someRings.rend(), count, pairs, increments, used);
      } else {
        fillOdd(x, a, someRings.begin(), someRings.end(), count, pairs, increments, used);
      }
    }
  }
}
```
其中用到的 fillOdd 如下：
```
inline int peerOf(const vector<int>& x, int index) {
  return x.size() - index - 1;
}

template<typename I>
void fillOdd(const vector<int>& x, vector<int>& a,
             I begin, I end, int& count, int pairs,
             vector<int> &increments, vector<int> &used) {
  for (auto ji = begin; ji != end; ++ji) {
    int j = *ji;

    // `j = *ji` 是最小元素。
    // 观察上面的图可以发现，最小元素后的第二个（即 `最小` -> 第一个 -> 第二个）
    // 会被填充到 `s(i)`。我们从 `s(i)` 开始填起，所以先跳过两个元素。
    j = x[x[j]];

    // 从 `s(i)` 开始填起
    int start = j;
    a[pairs + count] = j;

    int offset = pairs - 1;
    // 我们一对一对地填充。填完一对，跳过其它 `s(i)` 遍历需要的，然后进入下一层再填。
    int layers = 0;
    for (j = x[j]; j != start; j = x[j]) {
      // 跳过已填的。
      int slot = offset - used[layers];
      a[slot] = j;
      j = x[j];
      a[peerOf(x, slot)] = j;

      // 标记已填。
      used[layers]++;
      // 进入下一层。
      offset -= increments[layers];
      layers++;

      // 初始化 increments。
      if (increments[layers] == 0) {
        increments[layers] = increments[layers - 1];
      }
    }
    // 这个 `s(i)` 已经遍历完了，下一层不需要预留位子了。
    increments[layers]--;
    // 到 `s(i+1)`。
    count++;
  }
}
```
然后是偶数元环填充：
```
/**
 * @param evenPairs 偶数元环的 L(j) 之和，`a[evenPairs], a[peerOf(evenPairs)]` 之间已经被奇数元环填满了。
 */
void fillEvens(const vector<int>& x, const map<int, vector<int>>& rings,
               vector<int>& a, int evenPairs) {
  // 从元素个数从小到大。
  for (auto i = rings.begin(); i != rings.end(); ++i) {
    // 只填偶数元环。
    if (i->first % 2 == 0) {
      auto &someRings = i->second;
      for (auto ji = someRings.rbegin(); ji != someRings.rend(); ++ji) {
        // 类似奇数元环，跳过两个。
        int j = *ji;
        j = x[x[j]];
        int start = j;
        
        // 偶数元环的特点是不需要预留位子了。直接按顺序填即可。
        do {
          --evenPairs;
          a[evenPairs] = j;
          j = x[j];
          a[peerOf(x, evenPairs)] = j;
          j = x[j];
        } while (j != start);
      }
    }
  }
}
```
总的代码使用 fillEvens 和 fillOdds 后，输出 a 即可（a 元素从 0 开始，输出时需要把 a 的元素加回 1）。