题解：P10280 [USACO24OPEN] Cowreography G

· · 题解

Preface

提供一份严谨的数学证明。

感谢 @lupengheyyds 帮助证明了部分结论。

前置数学知识

Part 1.

可以发现，问题等价于将 s 中的每个 1 与 t 中的每个 1 两两配对，并最小化代价。

这里我们需要先证明一下这个“代价”是什么：

引理：将位置 x, y 交换并保持中间数不改变的最优移动次数为 \lceil (y-x)/k \rceil。（x, y 满足 x < y, s[x] \ne s[y]。）

证明：使用数学归纳法。当 y-x \le k 时结论显然成立。当 y-x > k 时，若 s[x] \ne s[x+k]，则我们可以直接交换 x, x+k，问题转化到 x+k, y 的情形；否则 s[x] = s[x+k]，我们则可以先对 x+k 和 y 进行交换操作，这时就有 s[x] \ne s[x+k] 了。

Part 2.

引理：如果有 a, b, c, d 四个位置满足 c > a > b 且 a > d，则绝对不会出现 (c, b) 配对、(a, d) 配对的情况。

对于 c < a < b 且 a < d 同理。

用人话表述，就是对于序列 s 中的所有 1，绝对可以分为若干段“全部向右匹配”或者是“全部向左匹配”的段。绝对不会出现“交叉”的情形。

证明：

  1. c > a > b > d

    如果无交叉配对，即 (c, a) 配对、(b, d) 配对，有代价：

    \left\lceil \dfrac{c-a}{k} \right\rceil + \left\lceil \dfrac{b-d}{k} \right\rceil

    如果有交叉配对，即 (c, b) 配对、(a, d) 配对，有代价：

    \left\lceil \dfrac{c-b}{k} \right\rceil + \left\lceil \dfrac{a-d}{k} \right\rceil

    显然有：

    \left\lceil \dfrac{c-a}{k} \right\rceil \le \left\lceil \dfrac{c-b}{k} \right\rceil, \left\lceil \dfrac{b-d}{k} \right\rceil \le \left\lceil \dfrac{a-d}{k} \right\rceil

    结论成立。

  2. c > a > d > b

    代价式子和上面是一样的。而由于此时有：

    \left\lceil \dfrac{c-b}{k} \right\rceil \ge \left\lceil \dfrac{c-a+d-b}{k} \right\rceil \ge \left\lceil \dfrac{c-a}{k} \right\rceil + \left\lceil \dfrac{d-b}{k} \right\rceil - 1

    故有：

    \begin{aligned} \left\lceil \dfrac{c-b}{k} \right\rceil + \left\lceil \dfrac{a-d}{k} \right\rceil &\ge \left\lceil \dfrac{c-a}{k} \right\rceil + \left\lceil \dfrac{d-b}{k} \right\rceil + \left(\left\lceil \dfrac{a-d}{k} \right\rceil - 1\right) \\ &\ge \left\lceil \dfrac{c-a}{k} \right\rceil + \left\lceil \dfrac{d-b}{k} \right\rceil \end{aligned}

    结论成立。

由于该结论成立，我们完全可以将整个序列拆成若干段来处理，每段内有“t 的前缀和 \ge s 的前缀和”或“s 的前缀和 \ge t 的前缀和”。因为二者是对称的，在接下来的推导中我们将以前者为例，即所有 s 中的 1 向右方 t 中的 1 配对。

Part 3.

注意：接下来我们就要开始推式子了，请你回顾一下前面的数学前置知识。

设 n 表示该段中 1 的个数，p(i) 为一个 1 \sim n 的排列，s_i, t_i 分别表示 s, t 内该段中第 i 个 1 的下标。则我们可以写出该段的代价表达式：

\sum_{i=1}^n \left\lceil \dfrac{t_{p(i)} - s_i}{k} \right\rceil

由于我们更喜欢向下取整，我们将其化为如下的形式：

\sum_{i=1}^n \left\lceil \dfrac{t_{p(i)} - s_i}{k} \right\rceil = - \sum_{i=1}^n \left\lfloor \dfrac{s_i - t_{p(i)}}{k} \right\rfloor

然后我们发现，如果将分数部分提出，我们将得到一个定值。令 x_i = \dfrac{s_i}{k}, y_i = -\dfrac{t_i}{k}，有：

\sum_{i=1}^n \lfloor x_i+y_{p(i)} \rfloor = \sum_{i=1}^n x_i + \sum_{i=1}^n y_i - \sum_{i=1}^n \{x_i + y_{p(i)}\}

于是我们需要最小化 \sum_{i=1}^n \{x_i + y_{p(i)}\}。

令 x_i' = \{x_i\}, y_i' = \{y_i\}，有：

\sum_{i=1}^n \{x_i + y_{p(i)}\} = \sum_{i=1}^n x_i' + \sum_{i=1}^n y_i' - \sum_{i=1}^n [x_i' + y_{p(i)}' \ge 1]

于是我们需要最大化 \sum_{i=1}^n [x_i' + y_{p(i)}' \ge 1]。

\begin{aligned}\sum_{i=1}^n [x_i' + y_{p(i)}' \ge 1] &= \sum_{i=1}^n \left[ \dfrac{s_i}{k} \bmod 1 + \left(-\dfrac{t_{p(i)}}{k}\right) \bmod 1 \ge 1 \right] \\ &= \sum_{i=1}^n \left[ s_i \bmod k + (-t_{p(i)}) \bmod k \ge k \right]\end{aligned}

于是我们需要最大化余数相加 \ge k 的对数。

不难想到如下贪心：让每个 (-t_i) 匹配最小的能够 \ge k 的 s_i \bmod k；如果找不到，那就匹配一个最小的 s_i \bmod k 以减少损失。换句话说，就是匹配第一个 \ge t_i \bmod k 的 s_i \bmod k，如果找不到就匹配最小的 s_i \bmod k。

用 set 维护，能在 O(n \log n) 的时间复杂度内解决本题。

代码嘛，本质上和其他题解是一模一样的，就不放了。