Help us understand the problem. What is going on with this article?

AtCoderBeginnerContest 102C - Linear Approximation

AtCoderBeginnerContest 102C - Linear Approximation

今日はこの問題。
結果的に求めたいものは

 |x - B1| + |x - B2| + ... + |x - BN|の最小値

これを最小にするxはB1, B2, ... BNの中央値(メディアン)になるということを利用して答えを出します。

ちなみにこういった距離のことをマンハッタン距離といいます。

マンハッタン距離(マンハッタンきょり、Manhattan distance)またはL1-距離は、幾何学における距離概念のひとつ。 各座標の差(の絶対値)の総和を2点間の距離とする。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const long long INF = 1LL << 60;
const ll C = 1000000000+7;

int main() {
    int N, total;
    cin >> N;
    vector<ll> A(N), B(N);
    for(int i=0; i<N; i++) cin >> A[i], B[i] = A[i] - i - 1;

    //medium(中央値を取る)
    sort(B.begin(), B.end());
    ll x = B[N/2];

    ll res = 0;
    for(int i=0; i<N; i++) {
        res += abs(x - B[i]); // |A| = max(A, -A)
    }
    cout << res << endl;
}

こんな感じ。定石みたいなのでしっかり抑えておきたい。

akilax
営業社員からエンジニアになりました。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away