(Hard) Minimum Difference in Sums After Removal of Elements

3*N 만큼 배열이 구성되어 있을 때, N개의 element를 배열에서 제외한 후
앞의 연속한 N개의 element를 더한 값을 first,
뒤의 연속한 나머지 N개의 element를 더한 값을 second라고 했을 때의
min(first - second)를 정답으로 구하는 문제이다.

시간 제한이 애매해서 어떻게 풀지 고민하다가

N개의 element를 first, second로 각각 구해서 연산해주는 방법을 활용했다.

N+1개의 element에서 first가 생긴다면, 1개의 elemen가 제외되고 큰 element들만 활용된다.
...

second도 같은 원리로 구해준 후 계산해주면 된다.

using ll = long long;
using pii = pair<int,int>;
class Solution {
public:
    long long minimumDifference(vector<int>& nums) {
        int N = nums.size() / 3;
        ll max_data[N*3];

        ll max_num = 0;
        priority_queue<int, vector<int>, greater<int>> lowest;
        for (int i = 2 * N; i < 3 * N; i++) {
            max_num += nums[i];
            lowest.push(nums[i]);
        }
        max_data[2 * N] = max_num;

        for (int i = 2 * N - 1; i >= N; i--) {
            lowest.push(nums[i]);
            max_data[i] = max_data[i + 1] + nums[i];
            max_data[i] -= lowest.top(); lowest.pop();
        }

        ll min_data[N*3];
        ll min_num = 0;
        priority_queue<int> highest;
        for (int i = 0; i < N; i++) {
            highest.push(nums[i]);
            min_num += nums[i];
        }
        min_data[N-1] = min_num;
        for (int i = N; i < 2 * N; i++) {
            highest.push(nums[i]);
            min_data[i] = min_data[i - 1] + nums[i];
            min_data[i] -= highest.top(); highest.pop();
        }
        ll result = 1e18;
        for (int i = N - 1; i < 2 * N; i++) {
            result = min(result, min_data[i] - max_data[i + 1]);
        }
        return result;
    }
};