算法进阶指南86页二叉堆问题

注意点：

1. set集合自动排序 set集合自动排序 set集合自动排序 自己也太弱了吧 以后还是要多多做题啊！！
2. 原来数学推导真的真重要，在没有思路的情况下从最简单的情况开始推导，逐步发现规律，这真的是太重要了吧。
3. 迭代器 写法 一定要记住啊，
4. 反证法真的太强了吧！
5. 假设 第 k 条边已经选好，那么与这K个点相邻的点事同进退的原则！选择这个边之后，我们将这个边连接点两点的左右两点都删掉，再加入一条 k - 2 到 k -1 和 k + 1 到 k + 2 的边 !!!
6. 再次惊叹下这个题的巧妙啊！

   #include<bits/stdc++.h>
   #define pr printf
   #define sc scanf
   #define fur( i,a,b) for(int i = a; i<= b ;i++)
   #define fdr(i,a,b) for(int i = a ;i>=b ;i--)
   using namespace std;
   const int N = 100000 + 5;
   typedef long long ll;
   int n,k;
   int l[N],r[N];
   ll d[N] = {0};
   typedef pair<ll,int> PLI;
   void delete_node(int p)
   {
    /*l[r[p]] = l[p];
    r[l[p]] = r[p];*/
    r[l[p]] = r[p];
    l[r[p]] = l[p];
   }
   int main()
   {
    //freopen("in.txt","r",stdin);
    sc("%d %d",&n,&k);
    set<PLI> s;
    for(int i = 0 ; i < n ;i++)cin>>d[i];
    //for(int i = 0 ; i < n ;i++)cout<<d[i]<<endl;
    for(int i = n - 1 ; i ; i --)d[i] -= d[i -1 ];
    d[0] = d[n] = 1e15;
    for(int i = 0 ; i < n ; i++){
        l[i] = i - 1;
        r[i] = i + 1;
        s.insert({d[i] , i });
    }
    ll res = 0;
    while(k-- ){
        set<PLI>:: iterator it  = s.begin();
        ll v = it->first;
        int p = it->second;
        int left = l[p],right = r[p];
        delete_node(left);delete_node(right);
        s.erase(it);
        s.erase({d[left] , left} );
        s.erase( {d[right] , right});
        d[p] = d[right] + d[left] - d[p];
        s.insert( {d[p] , p});
        res += v;
    }
    pr("%lld\n",res);
    return 0;
   }
   

```