[JOIGST 2024] 相聚 题解

· · 题解

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

本题有结论：将坐标序列排序后，最终河狸聚成的形态必然形如“将连续的 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 只河狸的最小代价，那么有如下两种转移：

时间复杂度为 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;
}