admin管理员组

文章数量:1529447

题目链接: Boats Competition

大致题意:

给定n个数构成的数组, 让我们自定义一个数s, 使得对于任选ai与aj(i≠j), 满足ai+aj=s的组合尽可能多.

解题思路:

由于本题数据较小, n最大只有50, wi最大也只有50, 所以s最大不会超过100. 我们不妨枚举出每种s的取值, 然后看看对于当前s值有多少种组合, 结果取最大即可.

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1E2 + 10;
int a[N], b[N]; //a数组存放n个数据(可以不要), b数组存放为x的值有多少个
int main()
{
    int t; cin >> t;
    while (t--) {
        memset(b, 0, sizeof b);
        int n; cin >> n;
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), b[a[i]]++;
        int res = 0; 
        for (int k = 2; k <= 2 * n; ++k) {
            int cou = 0; //s=k时的结果数量
            for (int i = 1; i <= k / 2; ++i) { //避免重复只枚举前一半即可
                if (b[i] && b[k - i] && i != k - i) { //要避免取到相同的数字情况
                    int temp = min(b[i], b[k - i]);
                    cou += temp;
                }
            }
            if ((k & 1) == 0) cou += b[k >> 1] >> 1; //是偶数, 可能由相同数字组成
            res = max(res, cou);
        }
        cout << res << endl;
    }
    return 0;
}

END

本文标签： Boatscompetition

版权声明：本文标题：Boats Competition 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dianzi/1726693014a1080908.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。