题解 P7273 【ix35 的等差数列】
lmrttx
2021-01-16 19:55:27
先赞美一下良心的出题人！
输出0得30分。
当然，这里讲一下正确的做法。
我们枚举公差 $d$，对于第 $i$ 个数，如果当前的首项为：
$$a_i-d×(i-1)$$
那么，这个数就处于当前的等差数列中，自然不用修改。
找出一组数据中，$a_i-d×(i-1)>0$ 的[众数](https://baike.baidu.com/item/%E4%BC%97%E6%95%B0/44796?fr=aladdin)所出现的次数，这个出现次数就是不需要修改的数的个数。
枚举 $d$ 就能跑过了。
用一个数组记录答案。
小优化：
$d≤w/(n-1)$ （显然，根据题意）
所以枚举的范围缩小。
对了，枚举时写 $n-1$ 会RE一个点，因为，$n$ 可以等于1。
而亲测后发现枚举到 $w$ 会T到只有70。
所以写成 $w/n$ 就可以了。
贴代码啦！
```cpp
int n,w,a[300001],t[300001],min1=2e9+10;
int main(){
scanf("%d%d",&n,&w);
for(register int i=1;i<=n;i++)scanf("%d",&a[i]),t[a[i]]++;
for(int i=1;i<=n;i++)min1=min(min1,n-t[a[i]]);
for(int d=1;d<=w/n;d++){
int cnt=0;
for(int i=2;i<=n;i++){
if(a[i]-d*(i-1)!=a[1])cnt++;
}
min1=min(min1,cnt);
}
printf("%d",min1);
return 0;
}
```
谢谢阅读qwq！