自动搬运

查看原文

来自洛谷，原作者为

	xuchenxi zsh忠实小迷妹 || Small_Vegetable_Chicken || sqs是神/bx

搬运于2025-08-24 22:30:51，当前版本为作者最后更新于2024-07-23 12:01:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

题意理解

给定两个数组 $A _ {i}$ 和 $B _ {i}$ 。对于任意 $1\le k \le n$ ，将前 $k$ 组数两两配成 $k$ 个数对 $(A _ {i} , B _ {j})$ 。求出所有数对的和 $(A _ {i} ^ {} + B _ {j} ^ {})$ 中最大值的最小可能值。

题目分析

一道贪心的好题。

贪心结论

升序排序后将 $A _ {i}$ 和 $B _ {n-i+1}$ 配成一对最优。

结论证明

不妨设 $A _ {i}$ 是 A 中最大的元素， $B _ {j}$ 是 B 中最小的元素。

若将 $B _ {j}$ 替换为 $B _ {k} ^ {}$ $(B _ {j} \le B _ {k})$ ，则 $A _ {i} + B _ {k} \ge A _ {i} + B _ {j}$ 。即替换后不优于替换前，得证。

暴力解法: 50pts

输入 $A _ {i}$ 和 $B _ {i}$ 后直接排序, 暴力查找数对和的最小值，复杂度 $O(n _ {} ^ {2} \log{n})$ 。

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000005;
int n;
int a[maxn],b[maxn];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
		sort(a+1,a+i+1);
		sort(b+1,b+i+1);
        int ans=0;
		for(int j=1;j<=i;j++)
        ans=max(ans,a[j]+b[i-j+1]);
        cout<<ans<<"\n";
	}
	return 0;
}

正解：桶排序

上面的暴力显然会超时。

优化：

• 观察到 $n$ 的范围虽然很大，但 $A _ {i}$ 和 $B _ {i}$ 的范围极小，所以想到桶排序。
• 将和相同的数对预处理掉一部分。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int maxa=105;
int n;
int a,b;
int x[maxa],y[maxa];
int cnta[maxa],cntb[maxa];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int ans=0;
		cin>>a>>b;
		cnta[a]++,cntb[b]++;
		for(int j=1;j<maxa;j++)
		{
			x[j]=cnta[j];
			y[j]=cntb[j];
		}
		int l=1;
		int r=100;
		while(l<=100)//优化1
		{
			while(!x[l] && l<=100) l++;
			while(!y[r] && r>=1) r--;
			if(l>100) break;
			ans=max(ans,l+r);
			int g=min(x[l],y[r]);//优化2
			x[l]-=g;
			y[r]-=g;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

END