Dotcpp  >  编程题库  >  蓝桥杯2022年第十三届决赛真题-好等差数列
题目 2741:

蓝桥杯2022年第十三届决赛真题-好等差数列

时间限制: 2s 内存限制: 320MB 提交: 76 解决: 5

题目描述

等差数列是指从第二项开始,每一项与它前一项的差为同一个常数的数列,这个常数称为等差数列的公差。公差为整数的等差数列称为“好等差数列”。

一个数列到“好等差数列”的距离定义如下:找到一个最小的非负整数 k,使得将这个数列中的 k 个数修改后(可以修改为任意值),数列可以变为一个“好等差数列”,就称这个数列到“好等差数列”的距离为 k。例如,数列 (1, 2, 3, 5) 到“好等差数列”的距离为 1,因为将最后一个数字修改为 4 之后, (1, 2, 3, 4) 就是一个公差为 1 的“好等差数列”。

小蓝现在有一个长度为 n 的数列 A = (a0, a1, · · · , an−1) 。小蓝会对这个数列进行 m 次修改操作,每次修改数列中的一个元素,每次修改过后,小蓝都想知道当前的数列到“好等差数列”的距离是多少,请你帮他计算。

输入格式

输入的第一行包含一个整数 n,表示数列的长度。

第二行包含 n 个整数 a0, a1, · · · , an−1,相邻两个整数之间用一个空格分隔。

第三行包含一个整数 m ,表示修改的次数。

接下来 m 行,每行包含两个整数 p, v,用一个空格分隔,表示将数列 A 中下标为 p 的元素修改为 v。

输出格式

输出一行包含 m 个整数,相邻两个整数之间用一个空格分隔,其中第 i 个整数表示经过前 i 次修改操作之后,数列到“好等差数列”的距离。 

样例输入

3
0 1 7
2
1 0
2 0

样例输出

1 0

提示

第一次修改后,数列 A = (0, 0, 7),它到“好等差数列”的距离为 1,即至少修改其中一个元素后数列 A 就可以变成“好等差数列”。有多种实现方案:1)将第三个元素更改为 0 变为 (0, 0, 0) 是一个“好等差数列”,公差为 0;2)将第一个元素更改为 −7 变为 (−7, 0, 7) 也是一个“好等差数列”,公差为 7。注意上述两种方案中提到的更改并不是真的对数列 A 进行修改,而是为了表述数列是如何转化到“好等差数列”的。

第二次修改后,数列 A = (0, 0, 0),他已经是一个“好等差数列”了,所以答案就是 0 。

对于 20% 的评测用例,1 ≤ n, m ≤ 10 ,0 ≤ ai , v ≤ 10;

对于 50% 的评测用例,1 ≤ n ≤ 100 ,1 ≤ m ≤ 1000 ,0 ≤ ai , v ≤ 10000 ;

对于所有评测用例,1 ≤ n, m ≤ 1000 ,0 ≤ ai , v ≤ 10000 ,0 ≤ p ≤ n − 1。注意,以上为输入数据的限制,在判断是否为“好等差数列”时,修改的数可以超过 0 至 10000 的范围。

标签