[UCPC][2019][예선] B번 풀이

풀이

문제의 조건에 따라서 m의 최대값은 15,000입니다. n의 최대값에 대한 1000에 대한 정렬의 시간 복잡도는 $nlogn 1000 * log(1000) = 3000$입니다.

매번 카드 합체를 진행할 때마다 정렬을 진행하면, 15000 * 3000 = 45,000,000이므로 1초 이상의 시간이 소요되는 것으로 생각됩니다.

때문에 priority_queue를 이용해서 전체 정렬을 하지 않고 푸는 방법을 생각해야 합니다.

priority_queue를 사용하는 방법은 구사과님의 블로그를 보고 따로 정리해봤습니다. 여기

코드

#include <vector>
#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

priority_queue<long long, vector<long long>, greater<long long> > pq;

int n, m;
long long t;
int main(void) {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &t);
		pq.push(t);
	}

	for (int j = 0; j < m; j++) {
		long long first = pq.top(); pq.pop();
		long long second = pq.top(); pq.pop();
		pq.push(first + second);
		pq.push(first + second);
	}
	long long ans = 0;
	while (!pq.empty()) {
		ans += pq.top();
		pq.pop();
	}
	printf("%lld\n", ans);
	return 0;
}