309271: CF1654E. Arithmetic Operations
Memory Limit:1024 MB
Time Limit:5 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Arithmetic Operations
题意翻译
* 给定一个长度为 $n$ 的序列 $a$。 * 问至少需要修改几个数才能使得 $a$ 变为一个等差数列。 * $n\leq 10^5$,$1\leq a_i\leq 10^5$。题目描述
You are given an array of integers $ a_1, a_2, \ldots, a_n $ . You can do the following operation any number of times (possibly zero): - Choose any index $ i $ and set $ a_i $ to any integer (positive, negative or $ 0 $ ). What is the minimum number of operations needed to turn $ a $ into an arithmetic progression? The array $ a $ is an arithmetic progression if $ a_{i+1}-a_i=a_i-a_{i-1} $ for any $ 2 \leq i \leq n-1 $ .输入输出格式
输入格式
The first line contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^5 $ ).
输出格式
Print a single integer: the minimum number of operations needed to turn $ a $ into an arithmetic progression.
输入输出样例
输入样例 #1
9
3 2 7 8 6 9 5 4 1
输出样例 #1
6
输入样例 #2
14
19 2 15 8 9 14 17 13 4 14 4 11 15 7
输出样例 #2
10
输入样例 #3
10
100000 1 60000 2 20000 4 8 16 32 64
输出样例 #3
7
输入样例 #4
4
10000 20000 10000 1
输出样例 #4
2