自动搬运

查看原文

来自洛谷，原作者为

	andychen_2012 **

搬运于2025-08-24 23:05:48，当前版本为作者最后更新于2024-11-08 15:10:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

根据非管理城市只能连一条边，每条道路至少联结一个管理城市，我们可以发现，在不给任意两个管理城市间连边的时候，整个图是一个菊花森林，菊花的根是管理城市。我们称管理城市的所有非管理城市儿子为该管理城市所管理的城市。（有点绕）

我们如果只考虑管理城市间的连边，那么必然是按编号顺序连边最优，付出的代价是最右的管理城市编号减去最左的管理城市编号。

接下来考虑管理城市与非管理城市的连边，我们发现一个管理城市所管理的区域肯定是连续的一段，且其是这一段区域的中心。证明如下：

1. 若管理城市管理的区域不是连续的一段，那么存在两个管理城市的管理区域互相穿插，比如说 1 C 1 2 2 1 1 C 2。其中 C 指代管理城市，左边的管理所有编号为 1 的城市，右边的管理所有编号为 2 的城市，那么将上面的管理区域改为 1 C 1 1 1 2 2 C 2 必然更优。也即，若两个管理城市编号分别为 $i,j(i<j)$，而 $i$ 管理城市 $a$，$j$ 管理城市 $b$，满足 $i<b<a<j$，则这两条连边的代价之和为 $a-i+j-b$，若 $i$ 管理 $b$，$j$ 管理 $a$，则代价和为 $b-i+j-a<a-i+j-b$。若 $i<j<a$，则 $i$ 与 $a$ 的连边代价为 $a-i>a-j$，因此需要将 $a$ 的管理城市改为 $b$。
2. 管理城市与其儿子的连边代价是两段连续和，即 $(1+2+\cdots+a)+(1+2+\cdots+b)$，其中 $a+b$ 即为其儿子的数量。只有当 $a,b$ 最接近时，该连续和最小。令 $a+b+1=s$，当 $s$ 为奇数时，和为 $(\lfloor \frac{s}{2} \rfloor)(\lfloor \frac{s}{2} \rfloor+1)$；当 $s$ 为偶数时，和为 $\lfloor \frac{s}{2} \rfloor^2$。

因此对于给定的 $n,c$，我们有代价关于管理城市 $x$ 的函数 $f(x)$ 如下：

$$f(x)=g(\lfloor \frac{n}{x} \rfloor)(x-(n-\lfloor \frac{n}{x} \rfloor x))+g(\lceil \frac{n}{x} \rceil)(n-\lfloor \frac{n}{x} \rfloor x)+cx+h(n,x) $$

其中 $g(x)=\begin{cases}\lfloor \frac{x}{2} \rfloor^2 & x \equiv 0 \pmod 2\\ (\lfloor \frac{x}{2} \rfloor)(\lfloor \frac{x}{2} \rfloor+1) & x \equiv 1 \pmod 2\end{cases}$，$h(n,x)=\begin{cases}n-2\lfloor \frac{\lceil \frac{n}{x} \rceil}{2} \rfloor-1 & n-\lfloor \frac{n}{x} \rfloor x >1\\n-\lfloor \frac{\lceil \frac{n}{x} \rceil}{2} \rfloor-\lfloor \frac{\lfloor \frac{n}{x} \rfloor}{2} \rfloor-1 & n-\lfloor \frac{n}{x} \rfloor x =1\\n-2\lfloor \frac{\lfloor \frac{n}{x} \rfloor}{2} \rfloor-1 & n-\lfloor \frac{n}{x} \rfloor x =0 \end{cases}$。

因此 $g(x)$ 单调递增，$h(n,x)$ 在 $n$ 固定时单调递增，$\frac{n}{x}$ 单调递减。对各函数增长速度进行分析，可以发现 $f(x)$ 是单峰，有最小值的。因此对其进行三分即可。