Solution-P11569

CaiZi · 2025-01-09 20:40:02 · 题解

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

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

考虑枚举 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;
}