BZOJ-1150: [CTSC2007]数据备份Backup

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;
}