自动搬运

查看原文

来自洛谷，原作者为

	lndjy 退役oier，偶尔参与比赛出题，tag是我另一个身份，有人认识吗（）

搬运于2025-08-24 22:28:18，当前版本为作者最后更新于2021-01-17 09:10:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

听说题解都被叉了，写一发能过 hack 数据的。

考虑枚举公差，设公差为 $k$。

显然 $k\le \frac{w}{n}$。

那么，我们需要 $O(n)$ 的复杂度来计算给定公差下的最小值。

因为是等差数列，所以第 $i$ 项 $a_i$ 于首项 $a_1$ 存在以下关系：

所以对于第 $i$ 项，该项不用修改当且仅当 $a_1=a_i-k\times(i-1)$。选择不用修改的最多的 $a_1$ 就是当前公差的最小次数。

然后这样被叉了会 WA。注意要判断 $a_n\le w$。$a_n=a_1+(n-1)\times k$。

#include<iostream>
using namespace std;
int n,w,ans;
int a[300005],c[300005],t[300005];
int main()
{
	cin>>n>>w;
	if(n==1)
	{
		cout<<0;
		return 0;
	}
	for(int i=1;i<=n;i++)
	cin>>a[i];
	ans=n;
	for(int k=0;1+(n-1)*k<=w;k++)
	{
		for(int i=1;i<=n;i++)
		if(a[i]-k*(i-1)>0&&a[i]-k*(i-1)+(n-1)*k<=w) t[a[i]-k*(i-1)]++,ans=min(ans,n-t[a[i]-k*(i-1)]);
		for(int i=1;i<=n;i++)
		if(a[i]-k*(i-1)>0) t[a[i]-k*(i-1)]=0;
	}
	cout<<ans;
 	return 0;
}