题解 | A. 一般图最小匹配

A. 一般图最小匹配

看大家都是用 DP 写的，这里提供一种反悔贪心的思路。

将 $A_{i}A\_i$ 排序。

注意到对于一个 $ii$，它连出的边权最小的边必然是 $\min \{\mathrm{\mid }{A}_i-A_{i-1}\mathrm{\mid },\mathrm{\mid }{A}_{i+1}-A_i\mathrm{\mid }\}\backslash min\{\backslash \{\; |\; A\_i\; -\; A\_\{i-1\}\; |\; ,\; |A\_\{i+1\}\; -\; A\_i|\; \backslash \}\}$。

设 $d_i=\mathrm{\mid }{A}_{i+1}-A_i\mathrm{\mid }d\_i\; =\; |A\_\{i+1\}\; -\; A\_i|$，最终答案一定是这 $n-1n-1$ 个元素选出 $mm$ 个元素。

有一个限制，每个节点只能在匹配中选择 $11$ 次。也就是当选择了 $d_{i}d\_i$ 之后，$d_{i-1}d\_\{i-1\}$ 与 $d_{i+1}d\_\{i+1\}$ 都不能再被选择。

考虑如果选择 $d_{i}d\_i$ 后不优，那么更优解一定同时选择了 $d_{i-1}d\_\{i-1\}$ 和 $d_{i+1}d\_\{i+1\}$。这个可以通过一次反悔来修正。

具体地，用一个堆维护全局最小值，选择了 $d_{i}d\_\{i\}$ 之后，用 $d_{i-1}+d_{i+1}-d_{i}d\_\{i-1\}\; +\; d\_\{i+1\}\; -\; d\_i$ 来代替 $ii$。同时要让新节点成为 $i-1i-1$ 的后继，$i+1i+1$ 的前驱，这个可以用链表来实现。

复杂度 $O(m{}_{2}n)O(m\; \backslash log\_2\; n)$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define SET(a,b) memset(a,b,sizeof(a))
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=5005, inf=1e15;
struct node {
	int val, id;
};
bool operator<(node a,node b) {
	return a.val>b.val;
};
int n, m, cnt, ans, a[N], v[N], pre[N], nxt[N], d[N];
priority_queue<node> q;
void update(node x) {
	int l=pre[x.id], r=nxt[x.id];
	v[l]=v[r]=1;
	pre[x.id]=pre[l], nxt[pre[l]]=x.id;
    nxt[x.id]=nxt[r], pre[nxt[r]]=x.id;
	d[x.id]=(l&&r)? min(d[l]+d[r]-d[x.id],inf):inf;
	// 选择d[1]或d[n-1]后不可能再反悔，设置成inf
	q.push((node){d[x.id],x.id});
}
signed main() {
	n=read(), m=read();
	for(int i=1;i<=n;++i) a[i]=read();
	sort(a+1,a+n+1);
	for(int i=1;i<n;++i) d[i]=abs(a[i+1]-a[i]), pre[i]=i-1, nxt[i]=i+1;
	for(int i=1;i<n;++i) q.push((node){d[i],i});
	nxt[n-1]=0;
	 for(int i=1;i<=m;++i) {
    	while(v[q.top().id]) q.pop(); 
		node x=q.top(); q.pop();     
        ans+=x.val;
        update(x);
    }
	printf("%lld\n",ans);
}