修改序列

题目链接：ybt高效进阶强化训练1-2-4

题目大意

给你一个序列，问你要至少修改多少个数，使得对于 $i=1\sim n-1$，有 $a_{i+1}=a_i+i$。

思路

首先不难发现，如果你确定了任意个一个位置，那别的位置都确定了。

而且某两个位置之间的数是有一一对应的关系。
那我们可以通过简单的计算算出要让当前位置不改动，第一个位置要是什么。

那我们找到的相同的，就是可以一起不修改的，其他的就是要修改的。
那我们用一个 map 实现即可。

代码

#include<map>
#include<cstdio>
#include<iostream>
#define ll long long

using namespace std;

int n, ans;
int a[100001];
ll pl[100001];
map <ll, int> st;

int main() {
	scanf("%d", &n);
	
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		st[1ll * a[i] - 1ll * (1 + i - 1) * (i - 1) / 2] = 0;
	}
	
	for (int i = 1; i <= n; i++) {//记录有多少个位置要第一个数是 x，得到 st[x]，再用 pl 数组记录 st[x]>0 的 x
		st[1ll * a[i] - 1ll * (1 + i - 1) * (i - 1) / 2] = st[1ll * a[i] - 1ll * (1 + i - 1) * (i - 1) / 2] + 1;
		if (st[1ll * a[i] - 1ll * (1 + i - 1) * (i - 1) / 2] == 1)
			pl[++pl[0]] = 1ll * a[i] - 1ll * (1 + i - 1) * (i - 1) / 2;
	}
	
	for (int i = 1; i <= pl[0]; i++)//找到同一个起点最多的
		ans = max(ans, st[pl[i]]);
	printf("%d", n - ans);//除了你选的起点的，其它的都要改
	
	return 0;
}