백준 14452 Cow Dance Show (USACO January 2017 Silver 1번)

문제 링크: https://www.acmicpc.net/problem/14452

14452번: Cow Dance Show

Binary Search

예시

5 8

4 7 8 6 4

state에 한꺼번에 올라갈수 있는 소들의 수 k를 기준으로 binary search를 돌리면 됨. k = 3일때로 예를 들면,

multiset: 4 7 8, time = 4 (여기서 첫번째 소가 빠지고 네번째 소가 들어와야 함)

multiset: 7 8 6 + 4 = 10, time = 7 (네번째 소가 들어올때 그 소가 stage에서 춤추는 시간 6이 아니라, 네번째 소가 춤을 끝내고 나가는 시각 6 + 4 = 10으로 update해줘서 넣어줌)

이런식으로 multiset이 빌때까지 반복하면서 time을 update해주면 됨.

#include <bits/stdc++.h>
using namespace std;
 
int n, t, a[10001], ans;
multiset<int> ms;
 
bool solve(int sz) {
    int time = 0;
    int idx = 0;
    while(sz-- && idx < n) {
        ms.insert(a[idx++]);
    }
    while(!ms.empty()) {
        time = *ms.begin();
        ms.erase(ms.begin());
        if(idx < n) {
            ms.insert(a[idx++] + time);
        }
    }
    return time <= t;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> t;
    for(int i = 0; i < n; i++) cin >> a[i];
 
    int lo = 0, hi = 1e6;
    while(lo <= hi) {
        int mid = (lo + hi) / 2;
        if(solve(mid)) {
            ans = mid;
            hi = mid - 1;
        }
        else lo = mid + 1;
    }
 
    cout << ans << '\n';
    return 0;
}