ARC_100_A / ABC_102_C - Linear Approximation

[zeikar]

Problem link

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

Problem Summary

N 개의 a 배열에서 적당한 b 값을 구해서 아래 식을 최소로 만드는 b 값을 찾는 문제.

Solution

먼저 자기 인덱스 + 1만큼 빼고 시작하자.
그러면 | a[i] - b | 의 최솟값을 찾는 문제가 되는데..
이건 중앙값을 쓰면 된다.

자세한 증명은 https://drken1215.hatenablog.com/entry/2019/06/15/114700 참고.

a[i]를 정렬한 다음 중앙값으로 b를 설정하고 정답을 구하면 된다.
위 중앙값을 골라야 한다는 사실을 모르면 쉽지 않은 문제.

Source Code

#include <iostream>
#include <algorithm>
using namespace std;

int a[200000];

int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];

		a[i] -= (i + 1);
	}

	sort(a, a + n);

	int median = a[(n - 1) / 2];

	long long ans = 0;
	for (int i = 0; i < n; i++)
	{
		ans += abs(a[i] - median);
	}

	cout << ans << endl;
}