题目分类：堆，贪心

题意：

给出n个点，取出端点不重复的m条线段使得总长度最小。

题解：

考虑到超级钢琴的思路，考虑每个节点开头的一段。

贪心，每次取出最短的一段。

发现这并不保证全局最优。

考虑像网络流一样给他反悔的机会，用两边的和减去被取出的一段来更新以前面的那个节点开头的最小值。

使用链表维护。注意删除需要记录这个点不能作为起点还是不能作为终点还是都不能。

程序：

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int pre[120000];
int next[120000];
priority_queue<pair<int,pair<int,int> > >pq;
int m,a[120000],n;
int del[120000],ans,delback[120000],val[120000];
int main()
{
	scanf("%d %d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(i!=1)
		{
			pq.push(make_pair(-a[i]+a[i-1],make_pair(i-1,i)));
			val[i-1]=a[i]-a[i-1];
		}
		if(i==1)pre[i]=-1,next[i]=2;
		else if(i==n)pre[i]=n-1,next[i]=-1;
		else pre[i]=i-1,next[i]=i+1;
	}
	for (int i=1;i<=m;i++)
	{
		while (del[pq.top().second.first]==1||delback[pq.top().second.second]==1)pq.pop();
		int x1=pq.top().first;
		int x2=pq.top().second.first;
		int x3=pq.top().second.second;
		ans-=x1;
		pq.pop();
	//	for (int j=1;j<=n;j++)
	//	{
	//		printf("%d %d %d %d %d %d\n",j,pre[j],next[j],del[j],delback[j],val[j]);
	//	}printf("------------------------------%d %d %d %d\n",x1,x2,x3,ans);
		if(pre[x2]==-1)
		{
			del[x2]=1;
			del[x3]=1;
			delback[x3]=1;
			delback[x2]=1;
			pre[next[x3]]=-1;
		}
		else if(next[x3]==-1)
		{
			del[x2]=1;
			del[x3]=1;
			delback[x3]=1;
			delback[x2]=1;
			next[pre[x2]]=-1;
		}
		else
		{
			del[x3]=1;
			delback[x2]=1;
			del[x2]=1;
			delback[x3]=1;
			pre[next[x3]]=pre[x2];
			next[pre[x2]]=next[x3];
			pq.push(make_pair(-(val[x3]+val[pre[x2]]+(x1)),make_pair(pre[x2],next[x3])));
			val[pre[x2]]=(val[x3]+val[pre[x2]]+(x1));
		//	printf("=-=-=-=-=%d %d %d\n",-(val[x3]+val[pre[x2]]+(x1)),pre[x2],next[x3]);
		}
	}printf("%d\n",ans);
	return 0;
}