0. 题面
题目描述
高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。
邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。
你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。
输入格式
第一行包含两个整数：第一个是村庄 \(V\) 的数量，第二个是邮局的数量 \(P\)。
第二行包含 \(V\) 个整数。这些整数是村庄的位置。
输出格式
第一行包含一个整数\(S\)，它是每个村庄与其最近的邮局之间的所有距离的总和。
样例 #1
样例输入 #1
10 5
1 2 3 6 7 9 11 22 44 50
样例输出 #1
9
提示
对于 \(40\%\) 的数据，\(V \leq 300\)。
对于 \(100\%\) 的数据，\(1 \leq P \leq 300\)，\(P \leq V \leq 3000\)，$1 \leq $ 村庄位置 \(\leq 10000\)。
1. 朴素算法
容易看出这是一道 DP 题。不妨令 \(a_i\) 为位置第 \(i\) 大的村庄的位置（约定\(a_0=-\infty\)，\(a_{V+1}=\infty\)），\(f_{i,j}\) 为修建 \(i\) 个邮局且最后一个邮局在 \(a_j\) 处时前 \(j\) 个村庄与其最近的邮局之间的所有距离的总和，\(w(l,r)\) 为在 \(a_l\) 和 \(a_r\) 处修建邮局后在 \(a_l\) 和 \(a_r\) 之间的所有村庄与其最近的邮局之间的所有距离的总和。不难得出以下递推式：
\[f_{i,j}=\begin{cases} \min_{k=1}^{j-1} \left\{ f_{i-1,k}+w(k,j) \right\} & 2 \le i \le P \\ w(0,j) & i = 1 \end{cases} \]答案即为 $$ans=\min_{j=1}^{V}{f_{p,j}+w(j,V+1)} $$
事实上，使用前缀和技术，\(w\) 函数可以在 \(\Theta(1)\) 的时间复杂度内计算。约定 \(mid=\lfloor{\dfrac{a_l+a_r}{2}}\rfloor\)，\(sum_i\) 为在位置 \(i\) 及其左侧所有村庄的位置值之和，\(cnt_i\) 为在位置 \(i\) 及其左侧所有村庄的数量，可以知道
\[\begin{aligned} w(l,r) &= \sum_{i=l}^{r} \min\{a_i-a_l\ , a_r-a_i\ \} \\ &= \sum_{i \ge l \ \land\ a_i \le mid}(a_i-a_l) + \sum_{i \le r \ \land\ a_i > mid}(a_r-a_i) \qquad //在\ mid\ 左侧的村庄离\ a_l 更近，在\ mid\ 右侧的村庄离\ a_r 更近 \\ &= \sum_{i \ge l \ \land\ a_i \le mid}a_i - \sum_{i \ge l \ \land\ a_i \le mid}a_l + \sum_{i \le r \ \land\ a_i > mid}a_r - \sum_{i \le r \ \land\ a_i > mid}a_i \\ &= (sum_{mid}-sum_{a_l-1})-a_l(cnt_{mid}-cnt_{a_l-1}) +a_r(cnt_{a_r}-cnt_{mid}) - (sum_{a_r}-sum_{mid}) \end{aligned} \]于是我们得到了一个时间复杂度为 \(\Theta(VP^2)\) 的算法。但是它太慢了，需要优化。
2. 决策单调性优化
设 \(f_{i,j}=f_{i-1,p_{i,j}}+w(k,p_{i,j})\) ，我们称 \(p_{i,j}\) 为 \(f_{i,j}\) 的“最优决策点”。可以知道，递推式 \(f\) 具有“决策单调性”，即对于每个 \(i，j\)，均有 \(p_{i,j} \le p_{i,j+1}\)。证明如下：
\[先放着，以后再证\\ 反正大概就是证明“四边形不等式”，即 w(a,c)+w(b,d)\le w(a,d)+w(b,c)\ (a\le b\le c\le d) ，\\ 进而证明 f具有单调性，即f_{i,j}\le f_{i,j+1}\\ （其实从f的意义上也能看出，因为两个邮局离得越远距离和就越大） \]因此可以发现，如果求得 \(p_i\)，则可以知道 \(p_j\le p_i(j<i)\)，\(p_j\ge p_i(j>i)\) ，这样我们枚举法求 \(p\) 时就可以排除许多无用状态。因此可以想到一个分治算法，代码如下：
void dfs(int l,int r,int ll,int rr){
//l,r: f下标范围
//ll,rr: p可能的范围
if(l>r)return;
int mid=(l+r)/2,p=0;
f[mid]=INF;
for(int i=ll;i<mid;i++){
if(f[mid]>g[i]+w(a[i],a[mid])){
f[mid]=g[i]+w(a[i],a[mid]);
p=i;
}
}//枚举求
dfs(l,mid-1,ll,p);
dfs(mid+1,r,p,rr);
}
不难发现这个算法的时间复杂度是 \(\Theta(VP)\) ，足以通过此题。完整代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXP=300,MAXV=3000,MAXX=10000,INF=0x3f3f3f3f;
int v,p,a[MAXV+5],cnt[MAXX+5],sum[MAXX+5],pre[MAXX+5],suf[MAXX+5],R,f[MAXV+5],g[MAXV+5];
int w(int l,int r){
int mid1=(l+r)/2;
return sum[mid1]-sum[l-1]-l*(cnt[mid1]-cnt[l-1])+r*(cnt[r]-cnt[mid1])-(sum[r]-sum[mid1]);
}
void dfs(int l,int r,int ll,int rr){
if(l>r)return;
int mid=(l+r)/2,k=0;
f[mid]=INF;
for(int i=ll;i<mid;i++){
if(f[mid]>g[i]+w(a[i],a[mid])){
f[mid]=g[i]+w(a[i],a[mid]);
k=i;
}
}
dfs(l,mid-1,ll,k);
dfs(mid+1,r,k,rr);
}
int main(){
ios::sync_with_stdio(false);
cin>>v>>p;
for(int i=1;i<=v;i++){
cin>>a[i];
cnt[a[i]]++;
sum[a[i]]+=a[i];
}
sort(a+1,a+1+v);
R=a[v];
for(int i=1;i<=R;i++){
cnt[i]+=cnt[i-1];
sum[i]+=sum[i-1];
}
for(int i=1;i<=R;i++){
pre[i]=i*cnt[i]-sum[i];
suf[i]=sum[R]-sum[i-1]-i*(cnt[R]-cnt[i-1]);
}
for(int i=1;i<=v;i++){
f[i]=pre[a[i]];
}
int ans=INF;
for(int i=2;i<=p;i++){
swap(f,g);
dfs(1,v,1,v);
}
for(int i=1;i<=v;i++){
ans=min(ans,f[i]+suf[a[i]]);
}
cout<<ans<<endl;
return 0;
}