ARC_100_A / ABC_102_C - Linear Approximation #25
Description
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;
}