网站建设立项申请,搜索引擎优化什么意思,个体商户取名字推荐,比较大的做网站的公司有哪些正题
CF1654E luogu 正题
给你一个正整数序列#xff0c;你可以让一个位置变成任意整数#xff0c;问你最少修改多少个数#xff0c;能使得其成为等差序列 解题思路
考虑根号分治
对于公差小于 n\sqrt{n}n 的#xff0c;直接枚举公差#xff0c;然后枚举所有点…正题
CF1654E luogu 正题
给你一个正整数序列你可以让一个位置变成任意整数问你最少修改多少个数能使得其成为等差序列 解题思路
考虑根号分治
对于公差小于 n\sqrt{n}n 的直接枚举公差然后枚举所有点计算首项
对于公差大于 n\sqrt{n}n 的由初始序列保留下来的点相差不大于 n\sqrt{n}n所以枚举每个点然后遍历后面的 n\sqrt{n}n 个点计算公差 code
#includecmath
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#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 i1;in;i)scanf(%d,a[i]);m320;for(int i0;im;i){for(int j1;jn;j)ansmax(ans,s[a[j]-i*jn*i]);for(int j1;jn;j)s[a[j]-i*jn*i]--;}for(int i1;im;i){for(int j1;jn;j)ansmax(ans,s[a[j]i*j]);for(int j1;jn;j)s[a[j]i*j]--;}for(int i1;in;i){for(int j1;j100000/mijn;j)if((a[ij]-a[i])%j0)ansmax(ans,s[(a[ij]-a[i])/j100000]1);for(int j1;j100000/mijn;j)if((a[ij]-a[i])%j0)s[(a[ij]-a[i])/j100000]--;}printf(%d,n-ans);return 0;
}
