题解：P11258 [GDKOI2023 普及组] 城市建设

andychen_2012 · 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) 如下：

其中 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) 是单峰，有最小值的。因此对其进行三分即可。