环环相扣：P3832 [SHOI2012]排序解答

gudzpoz · 2022-06-08 19:25:49 · 题解

本文以 CC BY-SA 4.0 发布。

题意简述

1. 对每一个 \{x_n\} 排列，我们把序列转化为
2. 对中间序列 \{x_{a_n}\}，我们按由 \{a_n\} 规定的字典顺序进行比较。

由环构造 \{a_n\}

对于一个 \{x_n\} 排列，它一定可以唯一分成多个这样的环状序列：

例如：

• 
• 

我们下面举例说明在我们想要构造的 \{a_n\} 中，\{x_n\} 中的环状结构某种程度上得到了保留。

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

对例如

这样一个环的一部分，假设我们的 \{a_n\} 如下：（顺序不影响）

则经转化后 \{z_n\} 变为：

也就是说，其中环里相邻的两个元素 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) 表示这个环里我们需要最优先配对的元素对数。

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

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

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

下面的图均没有画出两端剩余的元素。

• 如果 \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）。