P9562 [SDCPC 2023] Matching

题目描述

给定长度为 $n$ 的整数序列 $a_1,a_2,\cdots ,a_n$，我们将从该序列中构造出一张无向图 $G$。具体来说，对于所有 $1\le i<j\le n$，若 $i-j=a_i-a_j$，则 $G$ 中将存在一条连接节点 $i$ 与 $j$ 的无向边，其边权为 $(a_i+a_j)$。

求 $G$ 的一个匹配，使得该匹配中所有边的边权之和最大，并输出最大边权之和。

请回忆：无向图的匹配，指的是从该无向图中选出一些边，使得任意两条边都没有公共的节点。特别地，不选任何边也是一个匹配。

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入一个整数 $n$（$2\le n\le 10^5$）表示序列的长度。

第二行输入 $n$ 个整数 $a_1,a_2,\cdots ,a_n$（$-10^9\le a_i\le 10^9$）表示序列。

保证所有数据中 $n$ 之和不超过 $5\times 10^5$。

输出格式

每组数据输出一行一个整数，表示匹配的最大边权之和。

【样例解释】

对于第一组样例数据，最优方案是选择连接节点 $3$ 和 $5$，节点 $4$ 和 $7$，以及节点 $8$ 和 $9$ 的三条边，边权之和为 $(5+7)+(6+9)+(1+2)=30$。

对于第二组样例数据，由于每条边的边权都是负数，因此最优匹配不应该选择任何边，答案为 $0$。

对于第三组样例数据，由于图中不存在任何边，因此答案为 $0$。

输入输出样例 #1

输入 #1

3
9
3 -5 5 6 7 -1 9 1 2
3
-5 -4 -3
3
1 10 100

输出 #1

30
0
0

C++实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
int n,ans;
unordered_map<int,vector<int> >mp;
void solve(){
	mp.clear();
	n=ans=0;
	cin>>n;
	for(int i=1;i<=n;++i){
		int x;
		cin>>x;
		mp[i-x].emplace_back(x);
	}
	for(auto&p:mp){
		vector<int>vec=p.second;
		reverse(vec.begin(),vec.end());
		for(int i=0;i+2<=vec.size();i+=2){
			int sm=vec[i]+vec[i+1];
			if(sm<=0)break;
			ans+=sm;
		}
	}
	cout<<ans<<'\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容