P10280 Cowreography G

P10280 Cowreography G

贪心

本题的证明中涵盖了多种证明方法：分类讨论，交换两个，整体策略，堪称贪心证明之典范

符号约定

令 \(s_x\) 表示最初字符串的不同 \(1\) 位置，\(t_x\) 表示最终字符串的不同 \(1\) 位置

Theorem1：

交换 \(a_i,a_j(i>j,a_i\ne a_j)\) 的最优步数为 \(\lceil\frac{i-j}{k}\rceil\)。

Prove：

从 \(i\) 交换到 \(j\) 的最优步数一定不会低于 \(\lceil\frac{i-j}{k}\rceil\)。

• 若 \(i-j\le k\) 此式显然成立。

• 若 \(i-j>k\)

  • 当 \(a_{i+k}\neq a_{i}\) 时，可以先交换 \(a_i\) 与 \(a_{i+k}\)，再交换 \(a_{i+k}\) 与 \(a_{j}\)

  • 当 \(a_{i+k}=a_i\) 时，可以先交换 \(a_{i+k},a_j\)，再交换 \(a_i\) 与 \(a_{i+k}\)

  所以假设 \(i-j=t\) 成立则 \(i-j=t+k\) 成立。

由数学归纳可得，该引理成立。

Lemma1

若 \(s_1\le t_1\le s_2\le t_2\) ，则 \(s_1\) 与 \(t_1\) 交换，\(s_2\) 与 \(t_2\) 交换不劣于 \(s_1\) 与 \(t_2\) 交换，\(s_2\) 与 \(t_1\) 交换。

Prove

令 \(s_1=a,t_1=a+b,s_2=a+b+c,t_2=a+b+c+d,a,b,c,d\)

\[\def\dis#1#2{\lceil\frac{#1-#2}{k}\rceil} \def\val#1{\lceil\frac{#1}{k}\rceil} \def\down#1{\lfloor-\frac{#1}{k}\rfloor} \def\flow#1{\{-\frac{#1}{k}\}} \begin{aligned} &要证：\dis{t_1}{s_1}+\dis {t_2}{s_2}\le \dis{s_2}{t_1}+\dis{t_2}{s_1}\\ &即证：\val{b}+\val{d}\le\val{c}+\val{b+c+d}\\&即证：\down{b+c+d}+\down c\le \down b+\down d\\ &即证：\flow{b+c+d}-2\frac ck\le \flow b+\flow d\\ &即证：\flow c-2\frac ck\le [b+c+d\le -k]+[b+c+d\le -2k]\\ &\because \flow c-2\frac ck\le 0,[b+c+d\le -k]+[b+c+d\le -2k]\ge 0\\ &\therefore 此式成立，且上述过程步步可逆，原命题成立 \end{aligned} \]

Lemma2

若 \(s_1\le t_1\le t_2\le s_2\) ，则 \(s_1\) 与 \(t_1\) 交换，\(s_2\) 与 \(t_2\) 交换优于 \(s_1\) 与 \(t_2\) 交换，\(s_2\) 与 \(t_1\) 交换。

Prove

令 \(s_1=a,t_1=a+b,t_2=a+b+c,s_2=a+b+c+d,a,b,c,d\)

\[\begin{aligned} &要证：\dis{t_1}{s_1}+\dis {s_2}{t_2}\le \dis{s_2}{t_1}+\dis{t_2}{s_1}\\ &即证：\val{b}+\val{d}\le\val{c+d}+\val{b+c}\\ &\therefore 此式显然成立，且上述过程步步可逆，原命题成立\end{aligned} \]

Theorem2

最优的选取方案一定可以划分为若干段，使得对于每一段来说， \(\max s\le \min t\lor \max t\le\min s\)。

Prove

由 Lemma1 与 Lemma 2 易得。

Theorem3:

贪心策略：对于每个 \(s\) 或 \(t\)，找到前面第一个模 \(k\) 的余数比他大的数进行匹配。

Prove

对于划分的每一段，令 \(p(i)\) 是这一段的下标的一个排列。假设 \(s\le t\)（\(s>t\) 同理可证）。

则：\(ans=\sum_i \left\lceil \dfrac{t_{p(i)} - s_i}{k} \right\rceil = - \sum_i \left\lfloor \dfrac{s_i - t_{p(i)}}{k} \right\rfloor\)。

令：\(x_i=\frac {s_i} k,y_i=-\frac {t_i}k\)。

\[\sum_i \lfloor x_i+y_{p(i)} \rfloor = \sum_i x_i + \sum_i y_i - \sum_i \{x_i + y_{p(i)}\} \]

于是需要最小化 \(\sum_{i}\{x_i+y_{p(i)}\}\)

令 \(x_i'=\{x_i\},y_i'=\{y_i\}\)。

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

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

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

显然，用原命题的贪心策略可以是这个式子最大。

\(\square\)