백준 22254 공정 컨설턴트 호석 혼내주기

 

 

 

n개의 선물을 x시간 안에 제작하는데 걸리는 최소 공정의 갯수를 구하는 문제.

선물이 최대 100000개 이기 때문에 1과 100000사이의 공정 갯수를 parametric search로 찾으면 된다. 해당 공정 갯수로 가능한지 확인은 공정 갯수만큼 우큐(minheap)를 만든 뒤 n개의 선물을 다 넣었을 때의 최댓값이 x보다 작거나 같은지 확인하면 된다.

 

원래 파라메트릭 서치 나오면 항상 +1 -1 하는게 헷갈려서 삽질하는데, 한번에 풀었다. ㅋㅋ

 

 

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(v) v.begin(), v.end()

int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int arr[100005];
int n, x;

void input() {
    cin >> n >> x;
    for(int i = 0; i < n; ++i) cin >> arr[i];
}

bool simulate(int lines) {
    priority_queue<int> pq;
    for(int i = 0; i < lines; ++i) pq.push(0);

    for(int i = 0; i < n; ++i) {
        int top = -pq.top(); pq.pop();
        top += arr[i];
        pq.push(-top);
    }

    int ret = 2e9;
    while(!pq.empty()) {
        ret = -pq.top(); pq.pop();
    }
    if(ret <= x) return true;
    else return false;
}

int main() {
    fastio;
    input();

    int s = 1, e = 100000;
    while(s < e) {
        int m = (s + e) >> 1;
        if(simulate(m)) e = m;
        else s = m+1;
    }
    cout << s;
}