自动搬运

查看原文

来自洛谷，原作者为

	CaiZi 初三蒟蒻 || 坐标 FJ || ENFP-A || MC&PVZ&RS 玩家 || 出题团为 CZOI（80765）

搬运于2025-08-24 23:08:29，当前版本为作者最后更新于2025-01-09 20:40:02，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

假设有一个等差数列 $\{b_n\}$ 可以通过若干次操作得到。

根据等差数列的定义，我们可以知道 $\{b_n\}$ 只和首项 $b_1$ 以及公差 $d$ 有关，这个等差数列的和 $s$ 为：

$$s=\frac{n(b_1+b_n)}{2}=\frac{nb_1+nb_1+(n-1)d}{2}=\frac{2nb_1+(n-1)d}{2} $$

考虑枚举 $d$。假设我们正在计算某个固定的 $d$ 的答案。我们首先需要求出操作次数的最小值，然后可以通过不断给整个数列全部 $+1$ 来制造更多不同的等差数列。因为 $\sum a_i$ 固定，而操作次数等于 $s-\sum a_i$，所以我们需要求出 $s$ 的最小值。因为 $n,d$ 确定，所以我们需要求出 $b_1$ 的最小值，即对 $a_1$ 进行操作的次数的最小值。

我们可以先假设 $c_1=a_1$，得到等差数列 $\{c_n\}$。由于每次操作只能 $+1$ 不能 $-1$，因此如果有 $a_i>c_i$，则只能通过对 $a_1$ 进行 $a_i-c_i$ 次操作解决。因此 $\max\{a_i-[a_1+(i-1)d]\}$ 即为对 $a_1$ 进行操作的次数的最小值，注意这个值为负数的情况。然后此时套用 $s$ 的计算方法得到 $\{b_n\}$ 的和。

然后考虑 $d$ 的范围，最小值肯定是 $0$。而最大值需要满足 $a_1+(n-1)d\le a_n+k$，即最大值为 $\frac{a_n-a_1+k}{n-1}$，因此枚举 $d$ 的复杂度是 $O(\frac{V+k}{n})$，其中 $V$ 代表 $\{a_n\}$ 的值域。然后每次计算的复杂度是 $O(n)$ 的，总复杂度为 $O(n+V+k)$。

代码展示：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[1000001],b,c,x,y,z;
signed main(){
	cin.tie(nullptr)->sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b+=a[i];
	}
	for(int i=0;a[1]+(n-1)*i<=a[n]+m;i++){
		x=0;
		for(int j=1;j<=n;j++){
			x=max(x,a[j]-a[1]-(j-1)*i);
		}
		y=(2*a[1]+2*x+(n-1)*i)*n/2;
		z=m-y+b;
		if(z>=0){
			c+=z/n+1;
		}
	}
	cout<<c;
	return 0;
}