Codeforces Round #661-C Boats Competition

タイトルの説明:

各人の品質を与えて、2人の1組のグループを要求して、各組の2人の重量と他のグループの重量と等しくて、最大でどれだけのグループに分けることができることを求めます.

説明を入力:

1行目:t(1(leq)t(leq)1000).テストの個数を表します.2行目:n(1(leq)n(leq)50).最初のテストで参加者の数.3行目:n個の数字からなる配列w.n人の参加者の重量を表す.(1(leq)(w_i)(leq)n)残りのt-1テストはこれに類する.

出力の説明:

各試験例について、整数kを印刷する.kは、各試験例において分割される最大グループの個数を表す.
タイトルリンク:https://www.luogu.com.cn/problem/CF1399C
考え方:テーマのデータ範囲が小さいため、暴力的なやり方を使うことができます.しかし,配列wを直接遍歴することは難しいので,この場合は「執果インデックス」を考慮する必要がある.すなわち,各グループにおける2人の質量和のすべての可能性を遍歴することによって解く.(つまり、私たちが普段言っていることは考えられないから考えてもいいということです).コードは次のとおりです.

#include
#include
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t,n,x;
    cin>>t;
    while(t--)
    {
        cin>>n;
        vector cnt(n+1);
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            ++cnt[x];
        }
        int k=2*n,ans=0,res=0;
        for(int s=2;s<=k;s++)
        {
            for(int i=1;in)
                   continue;
                ans+=min(cnt[i],cnt[s-i]);
            }
            if(s%2==0) ans+=cnt[s/2]/2;
            res=max(res,ans);
            ans=0;
        }
        cout<