自动搬运

查看原文

来自洛谷，原作者为

	Aventurine_stone （已AFO）愿人生的赌局，赢的总是我们。

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

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

以下是正文

1. 题目分析

这道题一眼搜索或者动规，因为我看不出来怎么动规，所以准备用搜索解这道题。

2. 题目做法

(1) 直接暴力搜索 (12pts)

我们将 $r$ 当作题目中 $a$，$b$ 数组的长度，将 $c$ 当作搜索到哪一层了，这样我们便可以写出暴力代码：

__int128 ans;
__int128 x,y;
void dfs(int r,int c)
{
	if(c==r+1)
	{
		__int128 s=x*y;
		if(s>ans)
			ans=s;
		return ;
	}
	x+=a[c].x;
	dfs(r,c+1);
	x-=a[c].x;
	y+=a[c].y;
	dfs(r,c+1);
	y-=a[c].y;
}

此算法时间复杂度为 $O(2^n)$ 让我们再看看数据范围，$n\le3000$，这不得直接 T 飞？

(2) 整体贪心+局部搜索(100pts)

本蒟蒻也是看了第一篇题解才有的思路，我们发现，因为题目数据范围是随机的，并且值域非常大，所以 $a$ 和 $b$ 的值一般不会太接近，我们只需要取更大的那个数即可。

但是这样做会有缺点，如果有 $a$ 和 $b$ 比较接近的情况出现，便很容易举出反例，这一部分我们就只能用搜索解决。

于是，我们可以先将 $a$，$b$ 数组以 $\frac{a}{b}$ 为排序标准进行降序排列，然后取正中间的 $100$ 个左右的断点进行枚举，先将断点左边大部分数和右边大部分数加入总数中，再暴力搜索断点附近的一些数更新答案就行了。

求总和的代码大概是这样：

void sum(int k)
{
	x=0,y=0;
	//确定搜索范围
	int l=max(1,k-5),r=min(n,k+5);
	//整体贪心
	for(int i=1;i<l;i++)
		x+=a[i].x;
	for(int i=r+1;i<=n;i++)
		y+=a[i].y;
	//局部搜索
	dfs(r,l);
}

这样就可以将这道题切掉了。