CuteWisp

[C++] AtCoder Beginner Contest 186 D번 Sum of difference

13 Jan 2021 | PS

AtCoder Beginner Contest 186 D번 Sum of difference

문제

https://atcoder.jp/contests/abc186/tasks/abc186_d abc186_d

풀이

입력 받은 수열의 모든 pair의 차의 합을 구하는 문제

Ai - Aj 를 구한다고 할 때 j를 고정시키고 생각해보자

N = 3이며 A는 sort되어 있다고 가정해 보자. j = 2일때

  • A2 - A0
  • A2 - A1 = 2A2 - (A0 + A1) = jAj - Sj

여기서 S는 A의 누적합계이다.

j*Aj - Sj를 j= 0,1,…N 까지 반복하면 O(N)시간에 해결 가능

코드

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll,ll,ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc186/tasks/abc186_d
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    ll n;
    cin >> n;
    vll a(n);
    for(int i = 0;i<n;i++){
        cin >> a[i];
    }
    sort(all(a));
    ll ans=0, tmp=0;
    for(int i = 1;i<n;i++){
        tmp += ((a[i]-a[i-1]) * i);
        ans += tmp;
    }
    cout << ans;
 
    return 0;
}

Related posts