欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

Codeforces Round #661 (Div. 3) C.Boats CompetitionCompetition

程序员文章站 2022-03-21 18:38:50
题目链接思路:首先预处理出所有可能的两两相加得到的答案,然后去重处理,标记初始数组中每个元素出现的次数,并标记当前元素存在,然后枚举预处理后的两元素和标记元素是否存在。代码:#include#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=2e5+7;const int M=2e4+5;const doubl...

题目链接

思路:

首先预处理出所有可能的两两相加得到的答案,然后去重处理,标记初始数组中每个元素出现的次数,并标记当前元素存在,然后枚举预处理后的两元素和标记元素是否存在。

代码:

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=2e5+7;
const int M=2e4+5;
const double eps=1e-8;
const int mod=1e9+7;
const int inf=0x7fffffff;
const double pi=3.1415926;
using namespace std;
int vis[N],a[N],b[N],c[N];
signed main()
{
    IOS;
    int t;
    cin>>t;
    while(t--)
    {
        int n,ma=-1000,minb=1e9+7,ans=0;
        cin>>n;
        vector<int>vec;
        memset(vis,0,sizeof vis);
        memset(b,0,sizeof b);
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            vis[a[i]]=1;
            b[a[i]]++;
        }
        sort(a+1,a+1+n);
        int cnt=0;
        for (int i=1;i<=n;i++)
        {
            for (int j=i+1;j<=n;j++)
            {
                vec.push_back(a[i]+a[j]);
            }
        }
        sort(vec.begin(),vec.end());
        vec.erase(unique(vec.begin(),vec.end()),vec.end());
        int k=vec.size();
        for (int i=0;i<k;i++)
        {
            int t=0;
            for (int j=1;j<=n;j++)
            {
                int kp=vec[i]-a[j];
                if (kp>0&&vis[kp])
                {
                    if(kp==a[j]&&(b[kp]-c[kp])<=1)
                    {
                        continue;
                    }
                    int x=min(b[a[j]]-c[a[j]],b[kp]-c[kp]);
                    x=max(x,0LL);
                    if(kp==a[j])
                    {
                        t+=x/2;
                    }
                    else
                    {
                        t += x;
                    }
                    c[a[j]]+=x;
                    c[kp]+=x;
                }
            }
            memset(c,0,sizeof c);
            ans=max(ans,t);
        }
        cout<<ans<<endl;
    }
    return 0;
}

本文地址:https://blog.csdn.net/ACkingdom/article/details/107853537

相关标签: 思维