自动搬运

查看原文

来自洛谷，原作者为

	pigstd Hello, the cruel world.

搬运于2025-08-24 22:23:58，当前版本为作者最后更新于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;
}