在一个x轴上给你n个点,以及他们的坐标要你找k段使得2*k个点相连,然后求他们相连段的总距离.
这是个贪心问题,至于证明我就不证明了..有点复杂,直接说结论吧.就是选了一段后,旁边的那两段就不会选了,我们就要造一个新的段为a[left]+a[right]-a[id].然后插入集合里面去.代表多连接了一次.这样操作k次就是答案了.具体代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
const int N=1e5+5;
ll a[N],l[N],r[N],d[N];
void cut(int t)
{
    r[l[t]]=r[t];
    l[r[t]]=l[t];
}
int main()
{
    int n,k;
    cin>>n>>k;
    set<pi>s;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        d[i]=a[i]-a[i-1];
        l[i]=i-1;r[i]=i+1;
        if(i>1) s.insert({d[i],i});
    }
    d[1]=1e15;d[n+1]=1e15;
    ll ans=0;
    while(k--)
    {
        auto x=s.begin();
        ll v=x->first; ll id=x->second;
        s.erase(x);
        ll left=l[id]; ll right=r[id];
        d[id]=d[left]+d[right]-d[id];
        s.insert({d[id],id});
        s.erase({d[left],left}); s.erase({d[right],right});
        cut(left); cut(right);
        ans+=v;
    }
    cout<<ans<<endl;
    return 0;   
}

下面有个问题就是这个问题的转化.给你一个长度为n的序列,让你分成k段让你求所有段的总和最小.dp可解,但是复杂度是n*k.下面讲下贪心的做法.首先我们知道0肯定对结果没有任何的,那么就是分正负了,连续的正段一定是一起选的,连续的负段也是..那我们就可以把连续的正段和负段直接合并.然后题目要我们选m段,我们假设连续的正段一共有cnt段,假如cnt<=m.那么肯定直接输出正数的和就好了,否则的话,我们就必须删除cnt-m个正段,或者删除cnt-m的正段和负段,删除一个负段相当于把两个正段合并,也就相当于删除了一个正段.下面问题就变成了删除cnt-m个正段/负段使得这些段总和最小,我们来分析一下,是不是我们删除一个正段旁边的负段就不会删除了?这很显然吧,同理我们删负段旁边的正段也不会删了,因为删负段就把两个合并了啊--题目成功的变成了上个题,下面我们来说这个题该怎么做--哦,还有一个细节,假如边界为负就不行了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
const int N=1e5+5;
ll a[N],l[N],r[N];
void cut(int t)
{
    r[l[t]]=r[t];
    l[r[t]]=l[t];
}
int main()
{
    int n,k,m,g=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        ll xi;
        scanf("%lld",&xi);
        if(!xi)continue;
        if(!g|| a[g] * xi< 0)a[++g]+=xi;
        else a[g]+=xi;
    }n=g;
    set<pi>s;ll ans=0,cnt=0;
    for(int i=1;i<=n;i++)
    {
        l[i]=i-1;r[i]=i+1;
        s.insert({abs(a[i]),i});
        if(a[i]>0) ans+=a[i],cnt++;
    }
    while(k<cnt)
    {
        auto x=s.begin();
        s.erase(x);
        if(a[x->second]>0||(l[x->second]!=0&&r[x->second]!=n+1))
        {
            ll v=x->first; ll id=x->second;
            ll left=l[id]; ll right=r[id];
            a[id]+=a[left]+a[right];
            s.insert({abs(a[id]),id});
            s.erase({abs(a[left]),left}); s.erase({abs(a[right]),right});
            cut(left); cut(right);
            ans-=v; 
            k++;
        }
    }
    cout<<ans<<endl;  
    return 0;   
}