2020-2021:teams:i_dont_know_png:jagiellonianu2020

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:i_dont_know_png:jagiellonianu2020 [2020/07/15 23:09]
potassium
+++ 2020-2021:teams:i_dont_know_png:jagiellonianu2020 [2020/07/20 22:21] (当前版本)
nikkukun add C
@@ 行 1: / 行 1: @@
-嗡嗡嗡====== 2020 Petrozavodsk Winter Camp, Jagiellonian U Contest ======
+====== 2020 Petrozavodsk Winter Camp, Jagiellonian U Contest ======
 [[https://codeforces.com/gym/287055|比赛链接]]
@@ 行 26: / 行 26: @@
 总时间复杂度 $O(\max \{a_i\} \log \max \{a_i\})$。
+===== C - Bookface =====
+Upsolved by nikkukun.
+==== 题目描述 ====
+给 $n \leq 2 \times 10^5$ 个数 $x_1, x_2, \ldots, x_n$（$x_i \in [0, 3 \times 10^{11}]$）和一个参数 $d \in [1, 10^6]$，你可以将这个序列的值任意改动为其余非负整数，使得对任意的 $i \neq j$ 都有 $|x_i - x_j| \geq d$，代价为每个数的改变量绝对值之和。
+求最小代价。
+==== 解题思路 ====
+不妨考虑先将 $x$ 数组排序，并在维持相对位置的情况下，使得排序后数组 $x_{i+1} - x_i \geq d$，这样原题的条件便得到满足。
+先转化条件为非降序列：要求 $x_{i+1} - x_i \geq d$，则令 $x'_i = x_i - (i - 1) \cdot d$，就变成了令 $x'_{i+1} \geq x_i'$ 的条件。
+再保证所有数非负：对所有 $x_i' < 0$ 的数，都将其先改为 $0$，并将变化量统计在答案中。此时显然转化回 $x_i$ 的数组既非负，又满足了条件。同时，在 $x_i'$ 中由于所有数也非负，为了用最小代价将 $x_i'$ 变为非降，不会把某些 $x_i'$ 重新调回负数，这并不优。
+于是，现在问题变成让 $x'$ 数组非降，而这是经典 $L_1$ 问题，参考 [[.:nikkukun:isotonic_regression#l_1_问题 | 保序回归问题]]。

2020-2021/teams/i_dont_know_png/jagiellonianu2020.1594825776.txt.gz · 最后更改: 2020/07/15 23:09 由 potassium