1회 문제풀이 04 / ABC 102 C - Linear Approximation

ABC 102 C - Linear Approximation

【문제 개요】

스누케군은 길이 N의 정수열 A를 가지고 있습니다.
스누케군은 정수 b를 자유롭게 고릅니다. 이 때, Ai와 b + i가 떨어져있으면 스누케군은 슬픕니다.
더욱 구체적으로는 스누케군의 슬픔치는 다음 식으로 계산됩니다. 또 여기서 |x|는 x의 절대값을 의미합니다.

• |(A1 - (b + 1))| + |(A2 - (b + 2))| + … + |(AN - (b + N)) 스누케군의 슬픔치의 최소값을 구하시오.

【전제】

• 1 ≦ N ≦ 2x10^5
• 1 ≦ Ai ≦ 10^9
• 입력은 전부 정수이다.

【입력 형태】

N
A1 A2 ... AN

【출력 형태】

스누케군의 슬픔치의 최소치를 출력하시오.

【예시】

입력 예 1

5
2 2 3 5 5

출력 예 1

2

b = 0으로 설정하면 스누케군의 슬픔치는 |(2-(0+1))| + |(2-(0+2))| + |(3-(0+3))| + |(5-(0+4))| + |(5-(0+5))| = 2 가 됩니다. b에 어떤값을 넣더라도 슬픔치는 2미만이 될 수 없기때문에 답은 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

ABC 102 C - Linear Approximation

【문제 개요】

스누케군은 길이 N의 정수열 A를 가지고 있습니다.
스누케군은 정수 b를 자유롭게 고릅니다. 이 때, Ai와 b + i가 떨어져있으면 스누케군은 슬픕니다.
더욱 구체적으로는 스누케군의 슬픔치는 다음 식으로 계산됩니다. 또 여기서 |x|는 x의 절대값을 의미합니다.

• |(A1 - (b + 1))| + |(A2 - (b + 2))| + … + |(AN - (b + N)) 스누케군의 슬픔치의 최소값을 구하시오.

【전제】

• 1 ≦ N ≦ 2x10^5
• 1 ≦ Ai ≦ 10^9
• 입력은 전부 정수이다.

【입력 형태】

N
A1 A2 ... AN

【출력 형태】

스누케군의 슬픔치의 최소치를 출력하시오.

【예시】

입력 예 1

5
2 2 3 5 5

출력 예 1

2

b = 0으로 설정하면 스누케군의 슬픔치는 |(2-(0+1))| + |(2-(0+2))| + |(3-(0+3))| + |(5-(0+4))| + |(5-(0+5))| = 2 가 됩니다. b에 어떤값을 넣더라도 슬픔치는 2미만이 될 수 없기때문에 답은 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