[AtCoder] ABC 186 D – Sum of difference

2020年12月20日

問題

方針

\[ \sum_{i=1}^{N = 1} \sum_{j = i + 1}^{N} |A_i – A_j|\]

上式において、\( i = k \vee j = k\) となる \( k \ (1 \leq k \leq N)\) は \(N – 1\) 回現れます。つまり、\( A_k \) と固定したとき、\( |A_k – A_i| \) を計算する \( A_i \) は、

\[ 1 \leq i \leq N \wedge i \neq k \]

となります。したがって、\( A_k \) より小さい整数の個数を \( l \)とし、大きい整数の個数を \( r \) とすると、\( A_k \) の求める答えに対する影響度は、\( (l – r)A_k\) となります。これは、二分探索によって求めることができます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll N;
    cin >> N;
    ll A[N];
    map<int, int> m;
    vector<ll> v;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        v.push_back(A[i]);
    }
    
    sort(v.begin(), v.end());
    ll sum = 0;
    for (int i = 0; i < v.size(); i++) {
        auto it1 = lower_bound(v.begin(), v.end(), v[i]);
        auto it2 = upper_bound(v.begin(), v.end(), v[i]);
        ll l = it1 - v.begin();
        ll r = v.end() - it2;
        sum += (l - r) * v[i];
    }
    cout << sum << "\n";
    return 0;
}