题目大意：有n个点，k条链，每个点离原点有一定的距离。要你用k条链连接2k个点，使得k条链的长度最短。
首先每次肯定是链相邻的2个点，所以我们先把相邻2个点的差值求出来，得到有n-1个数的数列。
然后问题就变成“在这个数列中寻找k个互不相邻的点，使得它们的和最小”。
我们把所有的数扔进一个堆里，每次贪心找出最小的数，在答案里把它加上。
这时就会出现一个问题：假设我们贪心出了第i个数，那么有可能选第i-1个数和第i+1个数最终的结果优于选第i个数。
所以我们每次贪心时，把找到的那个数的前一个数和后一个数删掉，把“前一个数+后一个数-原数”的值扔进堆里，如果这个数被选，相当于选了前一个数和后一个数而不选原数。
取k个数的话，重复k次就行了。
处理数与数的前后关系可以用链表，求最小的数可以用堆。
完结撒花
1 #include<bits/stdc++.h> 2 #define M 200005 3 using namespace std; 4 struct node{ 5 int id,x; node(){id=x=0;} node(int ID,int X){id=ID; x=X;} 6 friend bool operator <(node a,node b){return a.x>b.x;} 7 }; priority_queue<node> q; 8 int a[M]={0},n,m,ans=0,pre[M]={0},nxt[M]={0},vis[M]={0}; 9 10 int main(){ 11 scanf("%d%d",&n,&m); 12 for(int i=1;i<=n;i++) scanf("%d",a+i),a[i-1]=a[i]-a[i-1]; 13 for(int i=1;i<n;i++){ 14 q.push(node(i,a[i])); 15 pre[i]=i-1; nxt[i]=i+1; 16 } 17 a[0]=a[n]=1e9; nxt[n]=n; 18 while(m--){ 19 node u; 20 do{u=q.top(); q.pop();}while(vis[u.id]); 21 ans+=u.x; int x=u.id; 22 vis[pre[x]]=vis[nxt[x]]=1; 23 a[++n]=a[pre[x]]+a[nxt[x]]-u.x; 24 pre[n]=pre[pre[x]]; nxt[pre[n]]=n; 25 nxt[n]=nxt[nxt[x]]; pre[nxt[n]]=n; 26 q.push(node(n,a[n])); 27 } 28 cout<<ans<<endl; 29 }