自动搬运

查看原文

来自洛谷，原作者为

	Nostopathy 壶关条件 https://www.luogu.me/article/moj9ohqn#，壶关私|吾与吾爱皆亡于高塔，君与君心皆存于盛夏

搬运于2025-08-24 23:04:40，当前版本为作者最后更新于2024-10-03 17:50:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

solution

我们把两种物品的权值没有被计入总和称为相互抵消。

因为相互抵消的两种物品最多只可能相差 $1$，所以通过枚举其中一种零食被抵消的数量，另外一种也能随之确定。

为了让得到的答案最大，我们需要贪心抵消权值较小的物品。所以对 $a$ 和 $b$ 排序后遍历一遍，不难求解。

代码贴上来：

#include<bits/stdc++.h>
using namespace std;
#define int long long
void read(int &n)
{
    int x=0,F=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            F=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    n=x*F;
}
void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
const int maxn=1E5+10;
int n, m, a[maxn], b[maxn];
int tota[maxn], totb[maxn];
int f__a(int x)
{
	if(x<=n)
	{
		return tota[x];
	}
	return 0;
}
int f__b(int x)
{
	if(x<=m)
	{
		return totb[x];
	}
	return 0;
}
void work()
{
	read(n);	for(int i=1; i<=n; ++i)	read(a[i]);
	read(m);	for(int i=1; i<=m; ++i)	read(b[i]);
	sort(a+1, a+n+1);
	sort(b+1, b+m+1);
	
	tota[n+1] = 0;	totb[m+1] = 0;
	for(int i=n; i; --i)	tota[i]=tota[i+1]+a[i];
	for(int i=m; i; --i)	totb[i]=totb[i+1]+b[i];
	int ans = LLONG_MIN;
	for(int i=1; i<=min(n, m); ++i)
	{
		if(i<=n&&i<=m)
			ans=max(f__a(i+1)+f__b(i+1), ans);
		if(i+1<=n&&i<=m)
			ans=max(f__a(i+2)+f__b(i+1), ans);
		if(i<=n&&i+1<=m)
			ans=max(f__a(i+1)+f__b(i+2), ans);
	}
	write(ans);
	cout << endl;
}
signed main(){
	//泥嚎，写题吧骚年
	int T;	read(T);
	while(T--) { work(); }
	return 0;
}

你的一个赞，对你只是举手之劳，对我却是最好的鼓励。

谢谢。