【Codeforces–1630B】Range and Partition

题意#

给定一个长度为 $n$ 的数组 $a$。

你需要确定一个范围 $[x,y]$，并将 $a$ 数组分成 $k$ 段，使得对于每一段，在范围 $[x,y]$ 以内的不同元素个数大于在范围 $[x,y]$ 以外的不同元素个数。

此处的 $x, y$ 都是权值，不是下标。

请求出任意一组使得 $(y-x)$ 最小的 $x,y$，并输出划分的方案。

数据范围：

• $t$ 组数据，$1\leqslant t\leqslant 3\times 10^4$。
• $1\leqslant k\leqslant n\leqslant 2\times 10^5$，$\sum n\leqslant 2\times 10^5$。
• $1\leqslant a_i\leqslant n$。

题解#

对于这道题，最根本的问题是最小化的 $(y-x)$，而具体的形式是如何划分整个序列。

我们可以发现，如果同时考虑这两个问题，事情会变得非常复杂，难以下手。

所以我们不妨暂且扔下具体的形式，去考察最根本的问题。

**性质：**划分为 $k$ 段时，在 $[x, y]$ 内的数总体上至少要比在此区间以外的数多 $k$ 个。

**证明：**每个段内至少多一个，一共多至少 $k$ 个。

做法：

先将整个序列从小到大排序，然后用一个大小为 $n-\lfloor\frac{n-k}{2}\rfloor$ 的滑动窗口去检测。

窗口两端的数就是 $[x, y]$，取 $(y-x)$ 的最小值即可确定 $[x, y]$。

推理一下可以发现，让每一段都多一个，可以使滑动窗口尽可能小，这样 $(y-x)$ 也会相应更小，同时这样的一组 $[x, y]$ 一定有可行的划分方案。

最后构造方案时也是每一段多一个就划开即可。