题目描述

又是一年 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。

题目分析：这是一个很有意思的题目，刚开始我想的是哪个数字不对然后就改哪个数字，最后记录一下改的次数，这样是不对的，只能过50%的数据，因为我们改动一个数据的时候，会影响到后序数字的判断，所以这样的方法显然是行不通的。

那么我们换一种方式，我们利用公式去构造一个数组，叫它原始数组。这个数组里面是从0开始的，左右的数都是用题目给出的公式求出来的，很显然，题目给出的数组和原始数组之间一一对应构成一个等差数列，因为题目给出的也必然是一串连续的数列，我们就利用等差性质去判断有多少个差值是与最多差值不同就行，符合的数字之间差值是相同的，需要改动的数字与原始数字之间的差值是不等于等差数列的差值。

正难则反，我们用一个map数组记录一下最多出现的数字（标准的等差数值），然后用总数减去它就是需要修改的数字的个数

以样例为例

原始数组b[n]---->0 , 1 , 3 , 6 ,10,15

题目数组a[n]---->3 , 4 , 6 , 8,13,18

等差数组mp[n]->3 , 3 , 3 , 2 ,3 , 3 由此可见只有一个数需要改变，因为他不符合等差数列的普遍值

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e6 + 10;
ll a[maxn], b[maxn];
map<ll, int> mp;
int n;
int main()
{
    scanf("%d", &n);
    for (int i = 2; i <= n; i++)
        b[i] = b[i - 1] + i - 1;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        mp[a[i] - b[i]]++;
        ans = max(ans, mp[a[i] - b[i]]);
    }
    printf("%d\n", n - ans);
    return 0;
}