题目概述

有 $n$ 个村庄，现在要建 $m$ 个邮局，一种方案的代价是每个村庄到最近的邮局的距离之和。

解题报告

我再来水一遍这道题……之前已经用了wqs二分去掉了一维状态，这时候DP的状态数，转移效率都已经很优秀了，但转移数还是 $O(n)$ 的，其实转移数也可以优化。

因为算贡献要用到中点所以斜率优化肯定是gg的，感性理解（打表）一下会发现，如果 $f_i$ 是从 $f_j$ 转移过来的，那么 $f_{k},k>i$ 肯定不会从 $f_t,t<j$ 转移过来。

说明决策具有不降性，由于是 $f$ 来转移 $f$ ，所以分治做法就跪了。那么我们可以用单调队列维护决策点控制的区间，每次新加入决策点的时候控制区间的右端点肯定是 $n$ ，左端点通过和队尾比较，二分一下就可以确定。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000;

int n,K,pos[maxn+5],Head,Tail,p[maxn+5],l[maxn+5],r[maxn+5],g[maxn+5];LL sum[maxn+5],f[maxn+5];

inline LL Sum(int L,int R){
    if (L>R) return 0;int mid=L+(R-L>>1),l=mid-L+1,r=R-mid+1;
    return sum[R]-sum[mid-1]-(LL)r*pos[mid]+(LL)l*pos[mid]-sum[mid]+sum[L-1];
}
#define Val(j,i) (f[j]+Sum((j)+1,(i))+C)
inline bool check(LL C){
    Head=1;Tail=0;p[++Tail]=0;l[Tail]=1;r[Tail]=n;
    for (int i=1;i<=n;i++){
        f[i]=Val(p[Head],i);g[i]=g[p[Head]]+1;int lst=-1;
        while (Head<=Tail)
            if (Val(p[Tail],l[Tail])>Val(i,l[Tail])) lst=l[Tail--]; else{
                int L=l[Tail],R=r[Tail];
                for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
                    Val(p[Tail],mid)>Val(i,mid)?R=mid-1:L=mid+1;
                if (L<=r[Tail]) lst=L,r[Tail]=L-1;break;
            }
        if (~lst) p[++Tail]=i,l[Tail]=lst,r[Tail]=n;if (Head<=Tail) {l[Head]++;if (l[Head]>r[Head]) Head++;}
    }return g[n]<=K;
}
int main(){
    scanf("%d%d",&n,&K);K=min(K,n);for (int i=1;i<=n;i++) scanf("%d",&pos[i]);
    sort(pos+1,pos+1+n);for (int i=1;i<=n;i++) sum[i]=sum[i-1]+pos[i];
    LL L=0,R=1e12;for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) check(mid)?R=mid-1:L=mid+1;
    check(L);printf("%lld\n",f[n]-L*K);return 0;
}