305135: CF978D. Almost Arithmetic Progression
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:35
Solved:0
Description
Almost Arithmetic Progression
题意翻译
Polycarp 喜欢等差数列,对于一个数列 $ [a_1,a_2,a_3,\dots,a_n] $,如果对于每个 $ i\,(1\le i < n) $,$ a_{i+1}-a_i $ 的值均相同,那么这个数列就是一个等差数列。例如,$ [42] $ ,$ [5,5,5] $ ,$ [2,11,20,29] $ 和 $ [3,2,1,0] $ 是等差数列,但是 $ [1,0,1] $,$ [1,3,9] $ 和 $ [2,3,1] $ 不是。 根据定义,任何长度为 $ 1 $ 或 $ 2 $ 的数列都是等差数列。 Polycarp 找到了一个只包含正整数的数列 $ [b_1,b_2,b_3,\dots,b_n] $ 。他只想最多将每个元素改变一次。换句话说,对于每个元素,有三种选项:自增 $ 1 $,自减 $ 1 $ 或者不变。 你需要找到对 $ b $ 中元素操作(每个只能操作一次)的最小次数,使 $ b $ 变成一个等差数列。 操作完成后的数列可以含有 $ 0 $ 。 **【输入格式】** 第 $ 1 $ 行有 $ 1 $ 个整数 $ n\,(1\le n\le 100\,000) $ ,表示 $ b $ 中元素的个数。 第 $ 2 $ 行包含一个数列 $ b_1,b_2,b_3,\dots,b_n \,(1\le b_i \le 10^9)$。 **【输出格式】** 如果无法使用上述的操作将数列变为等差数列,输出 $ -1 $ 。在另一种情况下,输出一个非负整数,表示要将 $ b $ 变为等差数列所需要改变的元素的个数。唯一允许的操作是元素的自增 $/$ 减(不能够对一个元素操作两次)。 **【说明/提示】** 在样例 $ 1 $ 中,Polycarp 应该将第 $ 1 $ 个元素加 $ 1 $ ,将第 $ 2 $ 个元素加 $ 1 $ ,将第 $ 3 $ 个元素加 $ 1 $ ,并且不改变第 $ 4 $ 个元素。所以,Polycarp 操作之后的数列为 $ [25,20,15,10] $ 。 在样例 $ 2 $ 中,Polycarp 不应进行操作,因为他的数列已经是等差数列了。 在样例 $ 3 $ 中,不可能通过上述的操作将数列变为等差数列。 在样例 $ 4 $ 中,Polycarp 应该只将第 $ 1 $ 个元素加 $ 1 $ 。操作之后的数列为 $ [0,3,6,9,12] $ 。题目描述
Polycarp likes arithmetic progressions. A sequence $ [a_1, a_2, \dots, a_n] $ is called an arithmetic progression if for each $ i $ ( $ 1 \le i < n $ ) the value $ a_{i+1} - a_i $ is the same. For example, the sequences $ [42] $ , $ [5, 5, 5] $ , $ [2, 11, 20, 29] $ and $ [3, 2, 1, 0] $ are arithmetic progressions, but $ [1, 0, 1] $ , $ [1, 3, 9] $ and $ [2, 3, 1] $ are not. It follows from the definition that any sequence of length one or two is an arithmetic progression. Polycarp found some sequence of positive integers $ [b_1, b_2, \dots, b_n] $ . He agrees to change each element by at most one. In the other words, for each element there are exactly three options: an element can be decreased by $ 1 $ , an element can be increased by $ 1 $ , an element can be left unchanged. Determine a minimum possible number of elements in $ b $ which can be changed (by exactly one), so that the sequence $ b $ becomes an arithmetic progression, or report that it is impossible. It is possible that the resulting sequence contains element equals $ 0 $ .输入输出格式
输入格式
The first line contains a single integer $ n $ $ (1 \le n \le 100\,000) $ — the number of elements in $ b $ . The second line contains a sequence $ b_1, b_2, \dots, b_n $ $ (1 \le b_i \le 10^{9}) $ .
输出格式
If it is impossible to make an arithmetic progression with described operations, print -1. In the other case, print non-negative integer — the minimum number of elements to change to make the given sequence becomes an arithmetic progression. The only allowed operation is to add/to subtract one from an element (can't use operation twice to the same position).
输入输出样例
输入样例 #1
4
24 21 14 10
输出样例 #1
3
输入样例 #2
2
500 500
输出样例 #2
0
输入样例 #3
3
14 5 1
输出样例 #3
-1
输入样例 #4
5
1 3 6 9 12
输出样例 #4
1