B小y的序列

链接：https://ac.nowcoder.com/acm/contest/7780/B 来源：牛客网  

又是一年 CSP，机房的oier都在刷题，alan却在发呆想着小y，正巧忽然听到隔壁机房某神zlk熟悉的声音：“找规律就可以了吧，这个序列感觉很熟悉啊，就是1,2,4,6,11这其实就是一个a[i+1]-a[i]=i的序列哦，突然隔壁的声音大了起来，zlk，你好像有个数写错了（大雾）~ 课后，alan在纸上写下了这个题目，让szm做：给一个长度为n的序列a，你希望改最少的数，使得这个序列满足a[i+1]-a[i]=i吗？1<=i<n。

输入描述:

第一行一个整数n； 第二行n个整数（每两个数之间有个空格），分别表示a[1]到a[n]。

输出描述:

输出一个整数Ans，表示最少需要改多少个数

示例1

输入

复制6 3 4 6 8 13 18

6 3 4 6 8 13 18

输出

复制1

1

备注:

对于30%的数据 n<=1000 对于100%的数据 n<=100000 输入的其他数据的绝对值均小于等于1e9

代码：

#include<bits/stdc++.h> using namespace std; #define ll long long const ll maxn=1e5+7; ll a[maxn],n,s; map<ll,ll>m; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } ll min1=0; for(int i=1;i<=n;i++) { s=0; ll u=a[i]-(i-1)*i/2; m[u]++; min1=max(min1,m[u]); } cout<<n-min1<<endl; return 0; }