题解 P7273 【ix35 的等差数列】
SSerxhs
2021-01-17 11:14:14
~~讨论区鲨疯了，我还找 EA 鲨了自己~~
~~FST 警告~~
由于值域为 $[1,w]$ 且公差 $d$ 非负，显然 $d\in[0,\frac{w-1}{n-1}]$
考虑枚举公差并 $O(nf(n))$ 计算，则复杂度为 $O(wf(n))$
具体计算方法是考虑假如 $a_i$ 不修改，那么新数列首项必定为 $a_i-(i-1)\times d$。
考虑枚举新数列的首项，那么答案就是 $n-cnt(a_1)$，其中 $cnt$ 是出现次数
新数列的首项范围是 $O(w)$ 的，但数量是 $O(n)$ 的，即只会通过上述柿子计算得出
那可以用一个 map 或者平衡树维护每个新首项的 $cnt$，取 $\max$ 即可
注意判断左右两边是否超出值域范围
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
std::mt19937 rnd(time(0));
inline int sj(int n)
{
unsigned int x=rnd();
return x%n+1;
}
#define rand fst
template<typename typC> void read(register typC &x)
{
register int c=getchar(),fh=1;
while ((c<48)||(c>57))
{
if (c=='-') {c=getchar();fh=-1;break;}
c=getchar();
}
x=c^48;c=getchar();
while ((c>=48)&&(c<=57))
{
x=x*10+(c^48);
c=getchar();
}
x*=fh;
}
template<typename typC> void write(register typC x)
{
if (x<0) putchar('-'),x=-x;
static int st[100];
register int tp=1,y;st[1]=x%10;x/=10;
while (x) y=x/10,st[++tp]=x-y*10,x=y;++tp;
while (--tp) putchar(st[tp]|48);
}
template<typename typC> void write(register typC *a,register int num)
{
for (register int i=1;i<=num;i++) write(a[i]),putchar(i==num?10:32);
}
#define space(x) write(x),putchar(32)
#define enter(x) write(x),putchar(10)
const int N=3e5+2,M=2e6+2,p=998244353;
inline void inc(register int &x,const int y)
{
if ((x+=y)>=p) x-=p;
}
inline void dec(register int &x,const int y)
{
if ((x-=y)<0) x+=p;
}
inline int ksm(register int x,register int y)
{
register int r=1;
while (y)
{
if (y&1) r=(ll)r*x%p;
x=(ll)x*x%p;
y>>=1;
}
return r;
}
int a[N];
map<int,int> s;
int T,n,m,d,i,j,k,x,y,z,ans,la;
int main()
{
read(n);read(m);
if (n==1) return puts("0"),0;
for (i=1;i<=n;i++) read(a[i]);
for (d=0;d*(n-1)<=(m-1);d++)
{
s.clear();la=0;
for (i=1;i<=n;i++) if (a[i]>(i-1)*d&&a[i]<=m-d*(n-i)) la=max(la,++s[a[i]-i*d]);
ans=max(ans,la);
}
printf("%d",n-ans);
}
```