P9562 [SDCPC2023] G-Matching

思路

易发现，如果 \(i\) 和 \(j\) 可以连边，\(j\) 和 \(k\) 可以连边，那 \(i\) 和 \(k\) 也可以连边，如果 \(x\) 不能和 \(i\) 连边，那 \(x\) 同样不能和 \(j,k\) 连边。所以我们可以考虑把所有可以连边的放在一起，这样就把所有点分成了若干部分，并且每个部分不可能连边，必然是分割开的。

同时，条件 \(i-j=a_i-a_j\) 可以转化为 \(a_i-i=a_j-j\)，所以我们只需要把所有 \(a_i-i\) 一样的放在一起就好了。

然后对于每一部分，我们每次取值最大的两个点，如果和大于 \(0\) 就代表有贡献，计入答案，否则就可以推出这个部分了，因为剩下的必定小于 \(0\)，无法对答案做出贡献。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int T,n,a;
unordered_map<int,vector<int>>m;//用来存每个部分
long long ans;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		m.clear(),ans=0;//多组数据记得清零
		for(int i=1;i<=n;++i) scanf("%d",&a),m[i-a].push_back(a);//记录每个部分
		for(auto i:m)//遍历
		{
			vector<int>v=i.second;
			sort(v.begin(),v.end());//排序
			for(int i=v.size()-1;i>=1;i-=2)//注意：这里是i>=1，而非i>=0。因为如果i=0，就代表只剩一个，不能计入答案
			{
				if(v[i]+v[i-1]>0) ans+=v[i]+v[i-1];
				else break;
			}
		}
		printf("%lld\n",ans);
	}
}