自动搬运

查看原文

来自洛谷，原作者为

	scp020 这是一个亖人 || 最后在线时间：2025年8月24日9时5分

搬运于2025-08-24 22:49:36，当前版本为作者最后更新于2023-08-18 22:52:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P9562 [SDCPC2023] G-Matching 题解

签到题，是这场比赛第三简单的题。

解法

题中说对于 $i - j = a_i - a_j$，我们从 $i$ 到 $j$ 连一条边权为 $a_i + a_j$ 的双向边。

对于这个式子，我们可以变形为 $a_i - i = a_j - j$，而且不难发现如果有一些数它们的 $a_i - i$ 都相同，则这些数互相之间都有连边。整张图会分为若干连通块（或孤立点），每个连通块内都是一个完全图。现在问题转化为求完全图的最大权匹配。

我们考虑在输入 $a_i$ 时将 $a_i$ 转化为 $a_i - i$ 存储，记为 $val_i$，这样 $a_i$ 可表示为 $val_i + i$。然后将所有点将 $val$ 作为第一关键字，将 $i$ 作为第二关键字降序排序。这样一段连续的 $val$ 相同的区间即为一个连通块。如果一个连通块内有奇数个点，我们就舍去 $a_i$ 最小的点，剩下的点两两匹配，如果有偶数个点，我们就两两匹配。注意，如果两两匹配时 $a_i + a_j < 0$，我们就舍弃这两个点。

代码

#include<bits/stdc++.h>
using namespace std;
namespace fast_IO
{
	/*
	快读快写，可忽略。
	*/
};
using namespace fast_IO;
#define int long long
int t,n;
int ans;
struct node
{
	int pos,val;
};
node a[100010];
inline bool cmp(const node &x,const node &y)
{
	if(x.val==y.val) return x.pos>y.pos;
	return x.val>y.val;
}
signed main()
{
	read(t);
	while(t--)
	{
		read(n),ans=0;
		for(int i=1;i<=n;i++) read(a[i].val),a[i].val-=i,a[i].pos=i;
		sort(a+1,a+n+1,cmp);
		for(int i=2,cnt=1;i<=n;i++)
		{
			if(a[i].val!=a[i-1].val)
			{
				cnt=1;
				continue;
			}
			if(cnt&1) ans+=max(a[i].val+a[i-1].val+a[i].pos+a[i-1].pos,0ll);
			cnt++;
		}
		write(ans),Putchar('\n');
	}
	fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
	return 0;
}