小y的序列

小y的序列:

题目告诉我们这是一个a[i]与a[i+1]相差i的序列，所以我们只需要枚举一个已经是这个比例来的数列，然后再用题目给的数据看看和这个数列的差是一样的数量有多少，取最多的那个就是答案。由于数据范围a[i]是1e9，这里我用的map时间复杂度O(nlog(n))，也许数据可以用数组过直接O(n)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
    ll s=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<1)+(s<<3)+(c^48);c=getchar();
    }
    return f*s;
}
const int N=1555555;
ll a[N];
int ans;
map<ll,int>q;
int main(){
    int n=read();
    for(int i=1;i<=n;i++){
        a[i]=a[i-1]+i-1;
    }
    for(int i=1;i<=n;i++){
        ll x=read();
        ans=max(ans,++q[x-a[i]]);
    }
    cout<<n-ans<<endl;
    return 0;
}