自动搬运

查看原文

来自洛谷，原作者为

	David_Mercury The love you take is equal to the love you make.

搬运于2025-08-24 22:56:28，当前版本为作者最后更新于2024-09-30 17:51:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

Preface

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

感谢

明了部分结论。

---

前置数学知识

• 定义 $\{x\} = x - \lfloor x \rfloor$，即 $x$ 的分数部分。它也可以表示为 $\{x\} = x \bmod 1$。

• $[P(x)]$ 为艾弗森括号，当命题 $P(x)$ 为真时值为 $1$，否则为 $0$。

• $\bmod$ 运算满足分配律，即 $c(x \bmod y) = cx \bmod cy$。

• $\lceil -x \rceil = -\lfloor x \rfloor$

---

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)$ 的时间复杂度内解决本题。

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