标签：cnt le 题解 mathtt 端点标签 Contestant Struggling 代价

\(\mathtt{Link}\)

CF1450F The Struggling Contestant - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

\(\mathtt{Description}\)

\(T\) 组数据。

一共有 \(n\) 道题，题号从 \(1\) 到 \(n\)，其中题号为 \(i\) 的题有一个标签 \(a_i\)。需要确定一个做完 \(n\) 道题的顺序，使得所做的任意连续两道题的标签均不相同，且连续两道题之间题号不相邻的次数尽可能少，求出这个次数的最小值。

\(\mathtt{Data} \text{ } \mathtt{Range} \text{ } \mathtt{\&} \text{ } \mathtt{Restrictions}\)

\(1 \le T \le 10^4\)；
\(1 \le a_i < n \le 10^5\)。

\(\mathtt{Solution}\)

首先这个数据范围看着也太强了，果然是 codeforces 的机子啊。

考虑到题目要求排列尽可能连着来，也就是“跳跃”的次数尽可能少。考虑一个做法：扫描一遍数组 \(a\)，如果有 \(a_i = a_{i + 1}\)，我们考虑在 \(i\) 和 \(i +1\) 中间切开。假设扫一遍之后我们已经切成了 \(k\) 段。

然后，两种操作：

将 \(k\) 段重排；
将某一段逆转（注意到题目中说题号相邻，所以下降 \(1\) 也是不计入代价的）。

这样一来，每段以内是不跳跃的，需要考虑的代价只有段与段之间。事实上，这样一定是最优的，因为明显交换段内的元素，没有任何利处。于是，逆转整个段可以考虑成只有段的端点互换顺序，因为我们根本不关心某一段的中间。

命题 A：代价不可能小于 \(k-1\)。

证明：

如果原序列合法，代价为 \(0\)，不小于 \(k - 1 = 1 - 1 = 0\)，成立。

如果原序列不合法，因为按照原始的题号序列，我们发现存在 \(k - 1\) 对 \(a_i = a_{i +1}\) 的矛盾。不妨设个例子，第 \(3\) 题和第 \(4\) 题标签相同，存在矛盾，怎么解决？我们需要换这两个题之一的位置。根据对称性我们考虑换第 \(4\) 题。注意：换位置后要保证第 \(4\) 题是合法的（也就是旁边的标签不再相同），否则换位置就没意义了（或者说可以换个更好的位置）。

如果换位置后的第 \(4\) 题不在序列的两端，那么第 \(4\) 题左右必定有两个题，而这两个题中，任何一个又不能是第 \(3\) 题（不合法），就算 \(4\) 的一边是 \(5\)，另一边呢？因此最少会产生 \(1\) 的代价；
如果换位置后的第 \(4\) 题在序列的两端，假设在序列的最左端。如果我们要试图让这次换位置没有任何代价，那么第 \(4\) 题的右侧必须是第 \(5\) 题，第 \(5\) 题的右侧必须是第 \(6\) 题……这明显不可能，\(1, 2, 3\) 题直接没位置了。假设在序列的最右端也同理。
可能有人要问：如果被换位置的不是第 \(4\) 题而是第 \(1\) 题呢？第 \(1\) 题在最左，然后第 \(2\) 个是第 \(2\) 题……怎么样，发现问题了吧，这不就是原序列吗？所以这样换位置（其实就是没换）不合法。
于是有小结论：一个矛盾中某一题被串开，就要至少花费 \(1\) 的代价。
因此无论如何，为了串开第 \(3\) 题和第 \(4\) 题，必定要至少花费 \(1\) 的代价。
如果两对矛盾没有公共的（不会出现第 \(4\) 题同时和第 \(3\) 题和第 \(5\) 题同时矛盾类似情形），明显就要至少花费 \(2\) 的代价。如果是 \(3\) 对则代价至少为 \(3\)，以此类推。
考虑两个矛盾有公共的情况，比如第 \(3\) 题和第 \(4\) 题标签相同，第 \(4\) 题和第 \(5\) 题标签相同。
如果我们考虑串开第 \(3\) 题花费 \(1\) 的代价，串开之后第 \(4\) 题和第 \(5\) 题明显还得有一个要串开，所以总共至少花费 \(2\) 的代价。先传开第 \(5\) 题同理。
如果先串开第 \(4\) 题呢？串开第 \(4\) 题至少要 \(1\) 的代价，那么谁在 \(3\) 和 \(5\) 中间呢？可以发现第 \(4\) 题被串开后 \(3\) 和 \(5\) 之间，无论不填题还是填了若干题，都会有至少 \(1\) 的代价。
所以即使有公共，也是多少对矛盾就有至少多少代价。
因此总共 \(k-1\) 对矛盾，就会有至少 \(k-1\) 的代价。

命题 B：当可以通过操作 \(k\) 个内部合法的段，产生一组合法的解时，定义 \(f_i\) 表示第 \(i\) 个标签作为段的端点出现的次数，那么 \(\forall 1 \le i \le n\)，有 \(f_i \le k +1\)。如果一个段的长度为 \(1\)，也就是 \(1\) 个元素，那么这个元素的标签会被记录 \(2\) 次，因为它同时充当了这个段的左端点和右端点。

证明：考虑这是产生的一个解：\([s_1, s_2], [s_3, s_4], \cdots , [s_{2k - 1}, s_{2k}]\)。\(s_{2i - 1}\) 表示重排后，第 \(i\) 个段的左端点，在原来的 \(a\) 数组中下标（其实就是题号）。\(s_{2i}\) 同理表示右端点对应的下标（也是题号）。

根据解的合法性，相邻段中，左面段的右端点的标签不能等于右面段的左端点的标签，也就是 \(a_{s_2} \ne a_{s_3}\)，\(a_{s_4} \ne a_{s_5}\)……，不过需要注意：\(a_{s_3} = a_{s_4}\) 是完全有可能的，也就是同一个段左右端点标签可以相同。

因此一个标签最多出现 \(k +1\) 次：在 \(s_1\)，\(s_{2k}\) 出现 \(2\) 次，剩下代表左面段右端点，和右面段左端点的 \(k - 1\) 对数中，只有 \(k-1\) 个可以是同一个标签。

这个命题成为我们的突破口，我们开始着手思考刚刚这个命题反过来还可不可以。

命题 C：当 \(\forall 1 \le i \le n\)，有 \(f_i \le k +1\) 时，可以构造一组解，它的代价是 \(k-1\)，是最优解。

证明：考虑重排让解合法是让 \(k\) 段降至 \(1\) 段的过程，考虑 \(k\) 归纳。

\(k = 1\) 时代价明显为 \(k-1\)，即 \(0\)。

\(k \ge 1\) 时。我们假设 \(x\) 使得 \(f_x\) 最大，也就是 \(x\) 是作为段的端点出现的次数最多的那个标签。我们考虑选取一个以某个标签是 \(x\) 的点为端点的段和另一个以某个标签是 \(y\) （\(y \ne x\)）的点为端点的段，把 \(x\) 那头和 \(y\) 那头直接合并即可。

这个端点是左端点还是右端点有要求吗？没有。别忘了还有一种操作是把段逆转，这个时候可以任意调换一个段的两个端点题号。因此可以随便合并。

下面我们把因为合并产生变化的变量上面加上撇号，用以和合并前的变量区分。于是有 \(f_x' = f_x - 1\)，\(f_y' = f_y - 1\)，\(k' = k - 1\)。前两条是合并的结果：\(x\) 作为段的端点出现的次数少了 \(1\)，\(y\) 同理。\(k\) 也是描述了合并的结果：段少了 \(1\)。

明显仍然有 \(f_x', f_y' \le k' +1\)。考虑标签 \(z\)，满足 \(z \ne x\) 且 \(z \ne y\)。在合并操作前，有 \(f_z \le 2k - f_x\)，这是因为所有 \(f\) 的总和就是 \(2k\)。还有 \(2k - f_x \le 2k - f_z\)，因为前面的 \(x\) 使得了 \(f_x\) 最大。因此有 \(f_z \le 2k - f_z\)，即 \(f_z \le k\)。因为 \(k' = k - 1\)，因此 \(f_z \le k' +1\)。

所以现在仍然满足 \(\forall 1 \le i \le n\)，有 \(f_i \le k +1\)。归纳成功。

此时证明了一定能构造出一组解，接下来证明它的代价是 \(k-1\)。

可以发现，最后的序列一定是 \(k\) 个段通过一定的顺序，每一段或正或反过来，拼在一起的。这 \(k\) 段中间明显不能产生任何代价，那么能产生代价的只有 \(k - 1\) 个接缝，代价最多是 \(k-1\)。前面又说代价最少是 \(k-1\)，所以其实代价就是 \(k-1\)，是最优解。

由命题 B 我们知道，\(\forall 1 \le i \le n\)，有 \(f_i \le k +1\) 是有解的必要条件。现在我们构造出的 \(k\) 不满足这个条件，就说明无解了吗？其实并不是。注意到，我们之前对 \(k\) 个段的分法：

扫描一遍数组 \(a\)，如果有 \(a_i = a_{i + 1}\)，我们考虑在 \(i\) 和 \(i +1\) 中间切开。

考虑分段的本质，我们分段是想让每一段的内部都不矛盾。所以上述的分法其实是使得内部不矛盾的情况下，让分段数量最少的方法——这样我们可以保证刚刚得到的 \(k-1\) 的代价是最小的。为了方便，我将这个称之为基础分段——它是满足合法性的，切片最少的分段方案。

但是现在我们 \(k\) 太小了，已经让 \(\forall 1 \le i \le n\)，有 \(f_i \le k +1\) 不成立了。我们发现：在这 \(k\) 个段的基础上，接着切仍然满足合法性。这个时候可以考虑再分多一点段，让 \(k\) 更大，以满足这个条件，然后转化为上面的情况。但是也不能让 \(k\) 盲目大下去，否则可能会破坏最优性。

现在我们的任务是：让 \(k\) 提高最少的量，使得 \(\forall 1 \le i \le n\)，有 \(f_i \le k +1\)。不妨假设，原先有标签 \(x\)，使得 \(f_x > k + 1\)。

我们发现，\(f\) 的总和最大就到 \(2k\)，所以对于任意一个标签 \(y \ne x\)，\(f_y \le k +1\)。也就是其实我们要处理的只有标签 \(x\)。

让 \(f_x > k +1\) 变成 \(f_x \le k +1\)，两个路线：降低 \(f_x\)，提高 \(k\)。我们知道，分段是不可能降低 \(f_x\) 的。

因此这里有个结论：我们分段不能让 \(f_x\) 增加，必须保证它不变。因为分一次段 \(k\) 只能增加 \(1\)，一旦 \(f_x\) 增加了 \(1\) 甚至以上，我们的分段就是无用的。

不能让 \(f_x\) 增加，等效于不能在标签为 \(x\) 的题的左侧或者右侧切一刀。

注意：这个不能在标签为 \(x\) 的题左右侧切的限制，是在我们处理好基本的内部不矛盾的情况下，发现 \(f_x > k + 1\) 之后才约定的限制。也就是说，它并不限制基础切片方案——毕竟这个是满足合法性的基本要求。

为了达成目的，我们要切 \(f_x - k - 1\) 刀，以形成 \(f_x - 1\) 段。那么答案就是 \(f_x - 2\) 了。

问题：我们一定能达到这个目的吗？

命题 D：当且仅当 \(cnt_x \le \lceil\dfrac{n}{2}\rceil\) 时，可以将数组切成 \(f_x - 1\) 个合法段。

证明：命题等价于，在基础切片方案之后，可以切 \(f_x - k - 1\) 刀满足均不在标签为 \(x\) 的题的左侧或右侧。

考虑分析 \(cnt_x\) 和 \(f_x\) 之间的关系。

设数组 \(c\)，长度为题目标签为 \(x\) 的连续段数量 \(L\)，记 \(c_i\) 表示第 \(i\) 个连续段的长度。于是有：

\[f_x = \Sigma[2c_i - 2] = 2cnt_x - 2L \]

这个式子的意思是，统计每一个连续段中，\(x\) 作为线段端点标签出现的次数，累加起来。每一段线段端点标签出现次数恰好是 \(2c_i - 2\)。

\(c_i = 1\) 时，\(2c_i - 2 = 0\)，符合实际情况（落单的一个标签不可能是线段端点，因为它左右并不矛盾，不分段）。
\(c_i \ge 2\) 时，这个式子其实在描述：这 \(c_i\) 个连续的标签 \(x\)，除了开头的 \(x\) 作为右端点出现一次，结尾的 \(x\) 作为左端点出现一次，中间所有 \(x\) 都会自己成为一个段，也就是作为左右端点，出现 \(2\) 次。符合实际情况。

发现入手点：整个数组基础切片后，不能在标签为 \(x\) 的题的左侧或者右侧切一刀。考虑补集，或者说反向思考方式：在标签为 \(x\) 的题左侧或右侧切一刀的方案。

基础切片会将每个连续的 \(x\) 段中间，相邻的所有 \(x\) 之间切好片。那么实际上我们应该避免的是：每个连续段 \(x\) 的左面不能切；每个连续段 \(x\) 的右面不能切。也就是总共不能切的有 \(2L\) 刀。

基础切片在 \(x\) 之间切的片，是 \(\Sigma[c_i - 1] = cnt_x - L\) 个。

我们会发现标签还有别的呢！假设其他标签（\(y\) 和 \(y\)，或 \(z\) 和 \(z\)）之间的基础切片有 \(m\) 个。

那么剩下能切的刀是 \(n - 1 - (cnt_x - L) - 2L - m = n - 1 - cnt_x - L - m\) 个。

发现还有个 \(k\) 没有计算。现在他代表的是基础切片的段数，他应该等于基础切片的总数 \(+ 1\)，那么它等于 \(cnt_x - L + m + 1\)。

\(f_x - k - 1 = 2cnt_x - 2L - (cnt_x - L + m + 1) - 1 = cnt_x - L - m - 2\)。

这个数是我们能切的刀数，它应该小于等于剩下能切的刀数。

\(cnt_x - L - m - 2 \le n - 1 - cnt_x - L - m\)。

推导，得到 \(cnt_x \le \lceil\dfrac{n}{2}\rceil\)。

Q：怎么想到的这个命题？怎么突然出现了 \(cnt_x\)？

A：其实这题的一开始，我就发现如果 \(cnt_x > \lceil\dfrac{n}{2}\rceil\)，那就一定无解。其实这个非常好想，根据鸽巢原理可以得到，这种情况下无论怎么调整，都会有两个标签为 \(x\) 的挨在一起。

举例：\(n = 7, cnt_1 = 5\)。初始状态：1 2 1 2 1 1 1

这样就根本不可能通过调整顺序让他们不挨着。

所以，考虑这样一个事：如果 \(cnt_x \le \lceil\dfrac{n}{2}\rceil\)，那就一定有解吗？大力推式子证明即可。

因此我们成功得到这个题的结论：

如果出现最多的标签次数 \(cnt > \lceil\dfrac{n}{2}\rceil\)，那么无解；否则一定有解。

扫描一遍数组 \(a\)，如果有 \(a_i = a_{i + 1}\)，我们考虑在 \(i\) 和 \(i +1\) 中间切开，切开的段数，记为 \(k\)。记录最大的 \(f_x\)，表示标签 \(x\) 作为线段端点的标签出现次数。

如果 \(f_x \le k + 1\)，答案是 \(k - 1\)；

否则，答案是 \(f_x - 2\)。

\(\mathtt{Time} \text{ } \mathtt{Complexity}\)

单个测试数据 \(\operatorname{O}(n)\)。

\(\mathtt{Code}\)

实现太简单，不想写。

标签：cnt,le,题解,mathtt,端点,标签,Contestant,Struggling,代价
From： https://www.cnblogs.com/crab-in-the-northeast/p/cf1450f.html

[CF1450F] The Struggling Contestant 题解