题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

不知道用map可不可以，尝试一下！！！

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <map>
#include <stdio.h>
using namespace std;
const int N=100010;
int n,k;
typedef long long LL;
LL d[N];   //每个点与前一点的距离
int l[N],r[N]; //每个点的左右相邻坐标数组
map<LL,int> m;  //每个点的“距离-坐标”元组

int del_node(int p)
{
    l[r[p]]=l[p];
    r[l[p]]=r[p];
}

int main()
{
    scanf("%d%d",&n,&k);
    int i;
    for(i=1;i<=n;i++)
    {
        cin>>d[i];
    }

    for(i=n;i>0;i--)
    {
        d[i]-=d[i-1];
        l[i]=i-1;
        r[i]=i+1;
        if(i>1)
        {
            m[d[i]]=i;  //将距离和坐标加入map
        }
    }

    LL res;
    while(k--)
    {
        auto it=m.begin();   //每次找距离最小的元素
        LL v=it->first;   //最短距离
        int p=it->second;  //下标

        m.erase(v);   //在map中删除距离最小节点及其左右相邻节点
        m.erase(d[l[p]]);
        m.erase(d[r[p]]);


        del_node(l[p]);  //在双向链表中改变p左右相邻节点的连接关系
        del_node(r[p]);
        res+=v;
        d[p]=d[l[p]]+d[r[p]]-d[p];  //更新p节点最短距离
        m[d[p]]=p;   //将更新距离后的节点p插入map
    }
    cout<<res<<endl;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla