14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)

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

현재 남아 있는 가장 작은 에너지를 가진 두 슬라임의 합성을 반복한다.

ei: i번 슬라임의 에너지
c(i): i번 슬라임에 의해 최종적으로 비용에 ei가 곱해진 횟수
어떤 시점에서 에너지가 작은 순으로 슬라임에 번호를 매겼다고 하자.
그러면 c(i)는 단조 감소 함수가 된다.
만약 어떤 x, y에 대해 c(x)<c(y) & x<y를 만족한다면 x, y번 슬라임을 바꿔 조합해서 더 작은 비용을 만들 수 있으므로 모순이 생기기 때문이다.

이제 t(>2)번 슬라임이 2번 슬라임보다 빨리 1번 슬라임과 합성했다고 하자.
그러면 c(t)=c(1)
세 슬라임에 의해 비용에 곱해진 값은 e1^c(1) * e2^c(2) * et^c(1) ... (1)
여기서 2번 슬라임과 t번 슬라임을 바꿔서 조합했다면 곱해진 값은
e1^c(1) * e2^c(1) * et^c(2) ... (2) (* 여기서 c(x)는 처음 방법에 대한 값임)
c(1) >= c(2), et >= e2 이므로
(1) / (2) = (et / e2)^{c(1)-c(2)} >= 1
따라서 (2)의 방법이 (1)의 방법보다 나쁘지 않다. 결과적으로 1, 2번 슬라임을 먼저 합성해도 최소 비용을 구할 수 있다.

시간복잡도는 테스트케이스마다 $O(n\lg n)$

#include<cstdio>
#include<queue>
#define mod int(1e9+7)
using namespace std;
int t, n;
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d", &n);
        priority_queue<long long> pq;
        long long c, t;
        while (n--) scanf("%lld", &c), pq.push(-c);
        int res = 1;
        while (pq.size() > 1) {
            t = pq.top(); pq.pop();
            t *= pq.top(); pq.pop();
            res = t%mod*res%mod;
            pq.push(-t);
        }
        printf("%d\n", res);
    }
    return 0;
}