反悔贪心，思维量非常大，重点如下：
1.d[i]存区间，表示i-i+1的长度。
2.二叉堆来维护最小值
3.每次只有两种可能，一种是取不相邻的边，另一种是取相邻的边，如果取相邻的边，那么必定是破坏之间的集合重组，在代码上显示的就是差值
4.合边操作并不是真的合边，而是差值刚好就能代表重组集合，在数学意义上相等，但是在物理意义上不等。
#include <iostream> #include <set> #include<queue> using namespace std; typedef long long LL; typedef pair<LL, int> pll; const int N = 100010; int n, k; int l[N], r[N]; LL d[N]; int vis[N]; void delete_node(int p){ r[l[p]] = r[p]; l[r[p]] = l[p]; } priority_queue<pll,vector<pll>,greater<pll> > q; int main(){ cin >> n >> k; for (int i = 0; i < n; i ++ ) cin >> d[i]; 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; q.push({d[i],i}); } LL res = 0; while (k -- ){ while(vis[q.top().second]) q.pop(); pll t=q.top(); q.pop(); int p = t.second, left = l[p], right = r[p]; vis[l[p]]=vis[r[p]]=1; delete_node(left), delete_node(right); res +=t.first; d[p] = d[left] + d[right] - d[p]; q.push({d[p],p}); } cout << res << endl; return 0; }