题解 P6785 【「EZEC-3」排列】

pigstd · 2020-08-27 08:02:18 · 题解

出题人来水一发题解

题意：让你找到一个排列，满足相邻的差互为相反数并且绝对值为k（首尾也是相邻的），求最大满足该条件的队列中各个数和

不妨设第1个数为x，那么第2个数就只能是x - k或者x + k，第三个数就还是x，依次类推 显然，一个满足条件的队列只能有两个数a,b，并且a - b = |k| 不妨设a < b，那么b = a + k，然后枚举a，对于每一个a，答案就是( a + a + k ) \times \min ( sum_{a} , sum_{b} )（sum_{x}表示示x的个数）

当k = 0时还要特判

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int M=1e6+10;
int sum[M*2],n,k,maxn,ans=-1;

signed main()
{
    cin>>n>>k;
    for (int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        sum[a]+=b,maxn=max(maxn,a);
    }
    if (k==0)
    {
        for (int i=0;i<=maxn;i++)
            if (sum[i]!=1&&sum[i])//注意因为p>=2,所以k=0时sum[i]>=2
                ans=max(ans,i*sum[i]);
        if (ans==-1)cout<<"NO";
        else cout<<ans;
        return 0;
    }
    for (int i=0;i<=maxn;i++)
    {
        int j=i+k;
        if (sum[i]&&sum[j])
            ans=max(ans,min(sum[i],sum[j])*(i+j));
    }
    if (ans==-1)cout<<"NO";
    else cout<<ans;
    return 0;
}