题目描述
传送门
题目大意：给出n个点，选出2k个点两两配对，每对的代价上两个点的坐标差，每个点只能选一次，求最小代价。
题解
因为k<=n/2，所以选中的每对点一定是直接相连的。
那么如果我们把每两个点之间的间距看成点权，得到n-1个点。那么问题就转换成给出n-1个点从中选取k个点，使选中的点不相邻。
把刚开始把所有的点加入优先队列，每次选取没有标记过的点更新答案。
加入一个点，那么他的nxt和pre都需要打上标记表示不能选。同时将该点的权值变成a[nxt]+a[pre]-a[x]，下次选中这个点表示放弃a[x]，选择pre,nxt两个点。
用链表维护每个点的nxt,pre即可。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#define N 200003
using namespace std;
struct data{
int x,v;
data(int X=0,int V=0){
x=X,v=V;
}
bool operator <(const data &a)const {
return v>a.v;
}
};
priority_queue<data> p;
int a[N],pos[N],n,m,mark[N],l[N],r[N],ans;
void solve(int i)
{
while (!p.empty()){
data t=p.top();
if (!mark[t.x]) break;
p.pop();
}
data t=p.top(); p.pop();
int x=t.x;
ans+=a[x];
a[x]=a[l[x]]+a[r[x]]-a[x];
int pre=l[x]; int nxt=r[x];
mark[l[x]]=mark[r[x]]=1;
r[x]=r[nxt]; l[x]=l[pre]; r[l[x]]=x; l[r[x]]=x;
p.push(data(x,a[x]));
}
int main()
{
freopen("a.in","r",stdin);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&pos[i]);
for (int i=1;i<n;i++) a[i]=pos[i+1]-pos[i];
n--;
for (int i=1;i<=n;i++) l[i]=i-1,r[i]=i+1;
a[0]=a[n+1]=1000000000;
for (int i=1;i<=n;i++) p.push(data(i,a[i]));
for (int i=1;i<=m;i++) solve(i);
printf("%d\n",ans);
}