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\)
标签：le,frac,val,sum,交换,Cowreography,P10280,dis From： https://www.cnblogs.com/lupengheyyds/p/18442440