河南萌新联赛2025第（四）A

A

观察到本题 的范围较小，考虑枚举 的值，然后统计序列 的长度，取所有情况的最大值即可,枚举范围1~10000

点击查看代码

#include <bits/stdc++.h>
using namespace std;
int main()
{int n;cin >> n;vector<int> a(10001);int x = 0;int ans;for (int i = 0; i < n; i++){cin >> x;a[x]++;}for (int i = 2; i <= 10000; i++){int res = 0;for (int j = 1; j <= i - j; j++){if (j == i - j){res += a[j] / 2;}elseres += min(a[j], a[i - j]) * 2;}ans = max(ans, res);}cout <<  ans << endl;return 0;
}

核心算法部分详细讲解

点击查看代码

for (int i = 2; i <= 10000; i++){int res = 0;for (int j = 1; j <= i - j; j++){if (j == i - j){res += a[j] / 2;}elseres += min(a[j], a[i - j]) * 2;}ans = max(ans, res);}cout <<  ans << endl;

1. 外层循环：遍历所有可能的和i：i从1遍历到2*MAXN，覆盖所有可能的两个数字之和，对于每个可能的和i，计算能组成这个和的数字对数res， 内层循环：寻找和为i的数字对： j从1遍历到i-j（即j <= i-j），这样可以避免重复计算，对于每个j，另一个数字就是i-j，这样(j, i-j)就是一个可能的数字对，其和为i 2.处理两种情况的数字对： 情况1：两个数字相同（j == i-j）： 这种情况下，数字对是(j, j) 能组成的对数等于j出现次数的一半（因为每两个j可以组成一对） a[j] / 2 * 2计算的是完整的对数（乘以2是因为后面解释的原因） 情况2：两个数字不同（j != i-j）： 这种情况下，数字对是(j, i-j),能组成的对数受限于两个数字中较少出现的次数min(a[j], a[i-j]) * 2计算这对数字能贡献的对数

再找最大值，此时ans即为求