每日一题：小y的序列

题目

最少修改几个数，使得数列满足 $a[i + 1] - a[i] = i$。$(n \in [1, 1e5], a[i] \in [-1e9, 1e9])$

Solution

先构造一个长度为 $n$ 满足题意的初始数列，然后将所给的数减去对应的初始构造的数，差值出现的次数最多的就是最长的满足题意的序列，要修改的就是剩余的那些数。

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, x, p = 0, res;
  unordered_map<int, int> mp;
  cin >> n >> x;
  res = mp[x] = 1;
  for (int i = 1; i < n; i++) {
    cin >> x;
    p += i;
    res = max(res, ++mp[x - p]);
  }
  cout << n - res << endl;
  return 0;
}