백준 13975 파일 합치기 3

백준 13975

백준 1715인 카드 정렬하기와 같은 문제
우선순위 큐에 모든 원소를 넣고 두개씩 빼서 더해주는 것을 우선순위 큐에 원소가 하나가 남을 때까지 반복하면 된다.

#include <bits/stdc++.h>
using namespace std;
int t, k;
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> t;

	while (t--) {
		priority_queue<long long, vector<long long>, greater<long long>>q;
		int x;
		long long sum = 0;

		cin >> x;

		for (int i = 0; i < x; i++) {
			int a;
			cin >> a;
			q.push(a);
		}

		while (1) {
			if (q.size() != 1) {
				long long a = q.top();
				q.pop();
				long long b = q.top();
				q.pop();

				q.push(a + b);
				sum += (a + b);
			}
			else {
				break;
			}
		}
		cout << sum << '\n';
	}
}