Description：

在一个数轴上有 $n$ 个点，从里面选出 $2k$ 个点组成 $k$ 组，每组点之间的距离和最小。

$1\le n \le 100000$

Solution：

首先发现每个点只会和他相邻的点连边，于是把位置数组查分，得到 $n-1$ 个长度，要求在这 $n-1$ 个中选出不相邻的 $k$ 个使得他们的和最小，可以像[[bzoj2288]POJ Challenge 生日礼物](http://localhost:4000/2018/09/04/bzoj2288/)一样做，即把所有的丢进一个堆里，每次取堆顶，但是可能会取相邻的两段，如果取了相邻的，一定会同时取两边，即如果序列为 $ABCDEF$ ，如果 $C$ 最小，但最终答案里有 $D$ ，那一定也选了 $B$ ，因为 $D$ 没有 $C$ 优，之所以放弃 $C$ 一定是因为放弃它能得到 $B$ ，所以每个数取出之后把他的权值设为 $val[pre]+val[nxt]-val[pos]$ 放回堆里，再把左右删除即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

int p[MAXN];

int lef[MAXN],rig[MAXN];

priority_queue< pair<int,int> > q;

#define fi first

#define se second

bool tag[MAXN];

int val[MAXN];

#define INF 0x3f3f3f3f

int main()

{

    scanf("%d%d",&n,&m);

    for(int i = 1;i <= n;++i)scanf("%d",&p[i]);

    int ans = 0;

    for(int i = 1;i < n;++i)

    {

        lef[i] = i - 1,rig[i] = i + 1;

        tag[i] = false;

        val[i] = p[i + 1] - p[i];

        q.push(make_pair(-val[i],i));

    }

    val[0] = val[n] = INF;

    rig[0] = 1;lef[n] = n - 1;

    --n;

    for(int i = 1;i <= m;)

    {

        pair<int,int> k = q.top();q.pop();

        if(tag[k.se])continue;

        ans += val[k.se];

        ++i;

        tag[lef[k.se]] = tag[rig[k.se]] = true;

        val[k.se] = val[lef[k.se]] + val[rig[k.se]] - val[k.se];

        rig[lef[lef[k.se]]] = lef[rig[rig[k.se]]] = k.se;

        lef[k.se] = lef[lef[k.se]];rig[k.se] = rig[rig[k.se]];

        q.push(make_pair(-val[k.se],k.se));

    }

    cout << ans << endl;

    return 0;

}