题目描述

塔子哥从一个神秘人那里获得了一个长度为$N$的数组。神秘人告诉塔子哥，塔子哥可以修改数组的一个元素，来改变数组的最小差异度。塔子哥想知道，当他修改第$i$个元素为多少时，数组的的最小差异度会最小？

思路：数学题

给定一个长度为$n$的数组$a$。求修改第$i$个元素为多少时，数组的的最小差异度会最小？

数组的最小差异度定义为：数组所有相邻元素差值的绝对值的和。

可以很容易发现，当修改第$1$个和第$n$个元素时，显然修改其为$a_2$和$a_{n-1}$最好。而对于其他元素，由于差异值的定义，可以令$a_i$为$a_{i-1}$与$a_{i+1}$之间任意一值，这样，$a_i$与$a_{i-1}、a_{i+1}$的差异值可以用如下公式计算$a_{i+1}-a_i+a_i-a_{i-1}=a_{i+1}-a_{i-1}$(如果$a_{i-1}\gt a_{i+1}$，交换它们的值即可)。

如果令$a_i\lt a_{i-1}$或$a_i\gt a_{i+1}$，那么他们的差异值为$a_{i+1}-a_i$或$a_i-a_{i-1}$，由于大小关系，一定比上面的值大。