自动搬运

查看原文

来自洛谷，原作者为

	yywlp 快递组万岁！！！

搬运于2025-08-24 22:59:09，当前版本为作者最后更新于2024-06-03 17:38:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

挺有意思的题。

题目中 $0\le a_i\le 10^6$ 是非常重要的限制，因为这让我们可以枚举 $k$。显然当

的时候后面的 $a_i$ 一定都不满足了，那么设 $M=10^6$，每次其实只用枚举前 $\frac{M}{k}$ 个 $a_i$ 即可，这个形式刚刚好是调和级数，复杂度 $\Theta(M\log M)$。

又通过题目中的定义：

$a_{i}=a_{1}+(i-1)k$，（$1\leq i\leq n$）。

发现这其实是一条直线 $y=kx+b$。

其中 $k$ 就是题中的 $k$，$b$ 就是 $a_1$。

所以枚举 $k$，枚举 $a_i$，当 $(i-1)\times k\ge 10^6$ 时停止枚举，同时以 $a_i-(i-1)\times k$ 为下标，$b_i$ 为值，开个桶存一下看哪个 $a_1$ 可以使直线碰到的点价值总和最大即可。

复杂度即为开始所说的 $\Theta(M\log M)$。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=1e6+10;
int n;
int a[M],b[M],sum=0;
int p[4*M];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)scanf("%lld",&b[i]),sum+=b[i];
	int ans=1e18;
	for(int i=0;i<=1e6;i++){
		for(int j=1;(j-1)*i<=1e6&&j<=n;j++)p[a[j]-(j-1)*i+2*M]+=b[j],ans=min(ans,sum-p[a[j]-(j-1)*i+2*M]);
		for(int j=1;(j-1)*i<=1e6&&j<=n;j++)p[a[j]-(j-1)*i+2*M]-=b[j];
	}
	cout<<ans<<endl;
}