[文章目录]
Description
数轴上有n个点，你需要将其两两配对成k对，使得每个点至多属于一对，并使所有对点之间的距离的和最小。n<=10^5
贪心选取，显然不会出现两对之间的距离交叉的情况，所以每对点必是相邻点。
将点黑白染色形成二分图，那么答案就是求k个匹配，使得该匹配对应权值和最小，即有限流的最小费用流。
不过10^5个点显然跑不过去，并且发现这个图很有规律，每条边选了，那么相当于将相邻两条边连接到一起，边权为两条边的权值和减去当前边的权值。
那么我们用链表+堆模拟这个过程就行了，时间复杂度O(nlogn)
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
const int inf=0x3f3f3f3f;
bool vis[N];
int s[N],pre[N],nxt[N],w[N];
int n,k,ans;
struct node
{
int id,w;
};
bool operator < (node x,node y){return x.w>y.w;}
priority_queue<node>q;
int main()
{
scanf("%d%d",&n,&k);
int i;
for(i=1;i<=n;++i) scanf("%d",s+i);
pre[0]=0; nxt[0]=1; pre[n]=n-1; nxt[n]=n; w[0]=w[n]=inf;
for(i=1;i<n;++i)
{
w[i]=s[i+1]-s[i];
nxt[i]=i+1; pre[i]=i-1;
q.push((node){i,w[i]});
}
int x;
while(k--)
{
while(vis[q.top().id]) q.pop();
x=q.top().id; q.pop();
ans+=w[x]; w[x]=w[pre[x]]+w[nxt[x]]-w[x];
vis[pre[x]]=vis[nxt[x]]=1;
if(pre[x]!=0&&nxt[x]!=n) q.push((node){x,w[x]});
pre[x]=pre[pre[x]]; nxt[pre[x]]=x;
nxt[x]=nxt[nxt[x]]; pre[nxt[x]]=x;
}
printf("%d",ans);
return 0;
}