题解 P7273 【ix35 的等差数列】

· · 题解

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

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

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

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

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

a_i=a_1+k\times (i-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;
}