【平衡规划】Arithmetic Operations（CF1654E）

本文主要是介绍【平衡规划】Arithmetic Operations（CF1654E），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

正题

CF1654E
luogu

---

正题

给你一个正整数序列，你可以让一个位置变成任意整数，问你最少修改多少个数，能使得其成为等差序列

---

解题思路

考虑根号分治

对于公差小于 $\sqrt{n}$ 的，直接枚举公差，然后枚举所有点，计算首项

对于公差大于 $\sqrt{n}$ 的，由初始序列保留下来的点相差不大于 $\sqrt{n}$，所以枚举每个点，然后遍历后面的 $\sqrt{n}$ 个点，计算公差

---

code

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 100100
using namespace std;
int n,m,ans,a[N],s[N*640];
int main()
{scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d",&a[i]);m=320;for(int i=0;i<=m;++i){for(int j=1;j<=n;++j)ans=max(ans,++s[a[j]-i*j+n*i]);for(int j=1;j<=n;++j)s[a[j]-i*j+n*i]--;}for(int i=1;i<=m;++i){for(int j=1;j<=n;++j)ans=max(ans,++s[a[j]+i*j]);for(int j=1;j<=n;++j)s[a[j]+i*j]--;}for(int i=1;i<=n;++i){for(int j=1;j<=100000/m&&i+j<=n;++j)if((a[i+j]-a[i])%j==0)ans=max(ans,++s[(a[i+j]-a[i])/j+100000]+1);for(int j=1;j<=100000/m&&i+j<=n;++j)if((a[i+j]-a[i])%j==0)s[(a[i+j]-a[i])/j+100000]--;}printf("%d",n-ans);return 0;
}

这篇关于【平衡规划】Arithmetic Operations（CF1654E）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---