Codeforces Round #553 (Div. 2) D. Stas and the Queue at the Buffet

D. Stas and the Queue at the Buffet

https://codeforces.com/contest/1151/problem/D

$$a_i(j - 1) + b_i(n - j)$$

위의 식을 다시 재구성 해보자. \( j(a_i - b_i) - (a_i - nb_i)\)

순서에 영향을 미치는 식은 \((a_i - b_i)\)이므로 이 값이 큰 순서대로 정렬해 주면 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
ll a, b, arr[100005];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    ll sumv = 0;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        arr[i] = a - b;
        sumv += b * n - a;
    }
    sort(arr, arr + n);
 
    for (int i = 0; i < n; i++) {
        sumv += (n - i) * arr[i];
    }
 
    cout << sumv;
    return 0;
}