P6170

Zelotz · 2021-09-28 17:51:34 · 题解

题目链接

本蒟蒻的第一篇题解，写得不好请指出，蟹蟹。

题意：

有 n 头奶牛，分布在一些房间，某些房间可能有多头牛，要让这些牛按顺时针移动，求使每一个房间刚好有一个奶牛的最小花费。

花费计算：如果一头奶牛穿过了 d 扇门，他消耗的能量为 d^2。

分析：

先把这个环看成一条链

首先说一个东西：如果有 1 头奶牛在 a 点，1头奶牛在 b 点，还有一个没有奶牛的 c 点，且 c>b>a，要想有一头奶牛在 b 点，一头奶牛在 c 点，方案 a \to b,b \to c 比方案 a \to c 好。

很容易知道这是对的，可以设 x=b-a,y=c-b，而 c-a=y+x，所以 (x+y)^2=x^2+y^2+2xy>x^2+y^2。

也就是说在如果一个房间的奶牛的移动算一个移动过程，移动过程中一头奶牛不要越过另一头没有移动的奶牛。

所以可以直接从一个起点开始，如果这个房间里有超过1头奶牛，就把这些奶牛移到依次后面每一个的房间的末尾，直到没有多余的奶牛可以移动为止。

留下房间里最后一头奶牛，也就是上一次最后一头牛，每一个房间都这么处理。

为了好写代码，可以留下最后一头牛，把这个房间里多余的奶牛移动到下一个房间，下一个房间再做处理。

问题是起点如何选择。

当一个起点是合法时，\sum\limits_{i=1}^{n}c_{i} \geqslant i。

不知道就枚举呗，反正 n 不超过 1000。

窝语文不好，只能描述成这样惹。

代码：

为每一个奶牛编号，为 1 \sim n。

用 d_i 来表示编号为 i 的奶牛走过的距离。

用 \texttt{vector} 来存每一个房间里的奶牛。