ARC 147 C. Min Diff Sum (600, 青)

• 問題文
• 正解コード(C++)

考察

• 異なる二点間の距離の総和を最小化したいです。
• 答えが0になる条件が誘導になっています。
• 右端最小～左端最大に集められると気づくのは難しい気がします。
• 詳細は以下の通りです。公式解説と同じですね。

外側から合わせるアプローチ

ソースコード

#include <iostream>
#include <algorithm>
#include <functional>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

int n;
int l[300000], r[300000];

signed main() {
    int i;

    cin >> n;
    rep(i, n) cin >> l[i] >> r[i];
    sort(l, l + n, greater<int>());
    sort(r, r + n);

    int ans = 0;
    rep(i, n) {
        if (l[i] <= r[i]) break;
        ans += (n - 1 - 2 * i) * (l[i] - r[i]);
    }

    cout << ans << endl;
    return 0;
}