백준 22878 / C++

https://www.acmicpc.net/problem/22878

22878번: 간단한 문제

 

[ 풀이 ] 

수학문제입니다. 두가지 잘 알려진 식을 이용합니다.

1. max(a, b)+min(a, b)=a+b

2. max(|a|, |b|)= abs((a+b)/2)+abs((a-b)/2) 

2번 식은 수직선에서 중점을 잡고 오른쪽 반 칸이 최댓값이므로 쉽게 증명됩니다. 

두 식을 이용하면, 식이 pi-pj 꼴 , qi-qj 꼴, (pi-qi)-(qi-qj)꼴 (pi+qi)-(pj+qj) 꼴 4가지가 나옵니다.

1가지는 대표적으로 구해봅시다. 

시그마 2개를 풀면 i=j 경우와 i<j, i>j 인 모든 1<=i,j<=N 쌍의 차이를 더한 것입니다.

i=j일땐 0이 되고, i<j와 i>j인 경우는 대칭성으로 같습니다. 

따라서 sigma(i<j) |pi-pj|를 구해서 2배해주면 됩니다. 저 합은 pi를 정렬한 후 O(n)에 구할 수 있습니다.

i<j인 모든 쌍의 차이는 정렬하고 구하든 그냥 구하든 모든 경우를 더하게 되므로 값이 일정합니다. 

이렇게 3번 더 해주면 됩니다. 차와 합 꼴은 2로 나누는 점에 유의합시다. 시간복잡도는 O(4NlogN)입니다. 

 

[ Code ] 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 1000010;
ll n, p[MAX], q[MAX], r[MAX], s[MAX];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> p[i];
    for (int i = 0; i < n; i++) cin >> q[i]; 
    for (int i = 0; i < n; i++) {
        r[i] = p[i] - q[i];
        s[i] = p[i] + q[i];
    }
    sort(p, p + n); sort(q, q + n);
    sort(r, r + n); sort(s, s + n);
    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        ans += 2 * (2 * i - n + 1) * (p[i] + q[i]);
        ans -= (2 * i - n + 1) * (r[i] + s[i]);
    }
    cout << ans << '\n';
}