自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

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

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

以下是正文

之前把这题搬进了模拟赛，直接把当时写的题解弄过来。

本题有结论：将坐标序列排序后，最终河狸聚成的形态必然形如“将连续的 $2$ 只河狸或 $3$ 只河狸分成一组”。如果将 $4$ 只或更多只河狸移动到同一个位置，那么必然不优——以 $4$ 只河狸为例，假设坐标分别为 $a_1,a_2,a_3,a_4(a_1\le a_2\le a_3\le a_4)$，那么如果全部移动到同一个位置，代价为 $|a_1-a_2|+|a_2-a_3|+|a_2-a_4|$，但是如果将它们两两分组，代价就为 $|a_1-a_2|+|a_3-a_4|$，显然后者不大于前者；更多只的情况可以类似地推导。

所以我们可以先将 $a$ 排序，在这之后进行动态规划。设 $f_i$ 为考虑了前 $i$ 只河狸的最小代价，那么有如下两种转移：

• $f_i\gets f_{i-2}+a_i-a_{i-1}$；（将 $i-1$ 和 $i$ 分组）
• $f_i\gets f_{i-3}+a_i-a_{i-2}$；（将 $i-2$、$i-1$ 和 $i$ 分组）

时间复杂度为 $O(n\log n)$。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<int> a(n),f(n);
  for(auto &i:a)cin>>i;
  sort(a.begin(),a.end());
  f[1]=a[1]-a[0],f[2]=a[2]-a[0];
  for(int i=3;i<n;i++)
    f[i]=min(f[i-2]+a[i]-a[i-1],i>3?f[i-3]+a[i]-a[i-2]:(int)2e9); // 进行 DP
  cout<<f[n-1]<<endl;
  return 0;
}