14452번: Cow Dance Show

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


$O(n\lg^2n)$

최소 t는 n에 대한 단조 감소 함수이므로 t<=t_max를 만족하는지 묻는 결정문제로 바꿔 풀 수 있다. 현재 댄스가 가장 빨리 끝나는 소를 pop하고 새로운 소를 추가하며 우선순위 큐를 관리하면 해당 n에 대한 최소 t를 구할 수 있다.

#include<cstdio>
#include<queue>
using namespace std;
int t, n, a[100000];
bool f(int x) {
    priority_queue<int> pq;
    for (int i = 0; i < x; i++) pq.push(-a[i]);
    for (int i = x; i < n; i++) {
        pq.push(pq.top() - a[i]);
        pq.pop();
    }
    while (pq.size() - 1) pq.pop();
    return -pq.top() <= t;
}
int main() {
    scanf("%d%d", &n, &t);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    int low = 1, high = n, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        f(mid) ? high = mid - 1 : low = mid + 1;
    }
    printf("%d", low);
    return 0;
}