问题 K: 三角函数最优拟合
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:371
解决:104
题目描述
我们称一个数列$\{a_n\}$是"整三角数列" , 当且仅当它符合通项公式: $a_i=A\cos(\pi \cdot i)+B \quad (A,B \in \mathbb{R},A \neq 0)$
现在给出一个数列$\{b_n\}$ ,在一次操作内,你可以选择一个数 $i , (1 \leq i \leq n)$,任意更改 $b_i$ 的值.
请你求出将 $\{b_n\}$ 改成"整三角数列"的最小操作数.
输入
第一行,输入一个整数 $n$. $(2≤n≤10^5,n\text{为偶数})$
第二行,输入$n$个整数,代表$b_1,b_2,...,b_n$ $(1≤b_i≤10^5)$
第二行,输入$n$个整数,代表$b_1,b_2,...,b_n$ $(1≤b_i≤10^5)$
输出
输出一行,一个整数,代表最小操作数
样例输入 复制
4
1 1 2 2
样例输出 复制
2
提示
两次操作,将数列改为$\{1,2,1,2\}$,此时符合通项公式 $b_i = \frac{1}{2} \cdot \cos(\pi i)+\frac{3}{2}$