ABC｜Linear Approximation

本篇博客还在持续修改润色中～

敬请期待～

AtCoder题解｜ABC 102C Linear Approximation

---

题目信息 📚

【题目描述】

Snuke has an integer sequence $A$ of length $N$.

He will freely choose an integer $b$. Here, he will get sad if $A_i$ and $b+i$ are far from each other. More specifically, the sadness of Snuke is calculated as follows:

• $\text{abs}(A_1 - (b+1)) + \text{abs}(A_2 - (b+2)) + \ldots + \text{abs}(A_N - (b+N))$

Here, $\text{abs}(x)$ is a function that returns the absolute value of $x$.

Find the minimum possible sadness of Snuke.

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• All values in input are integers.

If we choose $b=0$, the sadness of Snuke would be $\text{abs}(2-(0+1)) + \text{abs}(2-(0+2)) + \text{abs}(3-(0+3)) + \text{abs}(5-(0+4)) + \text{abs}(5-(0+5)) = 2$. Any choice of $b$ does not make the sadness of Snuke less than $2$, so the answer is $2$.

【输入】

The input is given from Standard Input in the following format:

$N$

$A_{1}$ $A_{2}$ … $A_{N}$

【输出】

Print the minimum possible sadness of Snuke.

【数据范围】

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• All values in input are integers.

【输入样例1】

5
2 2 3 5 5

【输出样例1】

2

If we choose $b=0$, the sadness of Snuke would be $\text{abs}(2-(0+1)) + \text{abs}(2-(0+2)) + \text{abs}(3-(0+3)) + \text{abs}(5-(0+4)) + \text{abs}(5-(0+5)) = 2$. Any choice of $b$ does not make the sadness of Snuke less than $2$, so the answer is $2$.

【输入样例2】

9
1 2 3 4 5 6 7 8 9

【输出样例2】

0

【输入样例3】

6
6 5 4 3 2 1

【输出样例3】

18

【输入样例4】

7
1 1 1 1 2 3 4

【输出样例4】

6

【题目来源】

https://atcoder.jp/contests/abc102/tasks/arc100_a

---

题目解析 🍉

【题目分析】

【C++代码】