과부하 방지 (백준 31396)

안녕하세요. 오늘은 과부하를 방지할 거예요.

문제

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

아이디어

이 문제는 파라메트릭 서치를 통한 결정문제로 바꿀 수 있습니다.
x개의 전자기기가 가능한지 보려면 D값이 큰 순서대로 x개를 확인해서 그 x개가 가능한지 그리디하게 확인하면 됩니다.

현재 콘센트로부터 i개 떨어진 칸에 있다면 일단 D값이 i인 전자기기를 다 넣습니다. 만약 멀티탭이 부족하다? 그러면 false입니다. 아니면 남은 공간에 멀티탭을 큰 순서대로 채워넣습니다. 만약 그래도 공간이 남으면 멀티탭을 다 썼다는 뜻이므로 남은거를 다 넣을 수 있는지 확인해주면 됩니다. 남은 공간이 없다면 i++로 다시 시작하면 되고요.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

vector <ll> multi, furniture;
ll N, K, M;

ll furni_cnt[202020] = { 0 };
bool able(ll idx)
{
    for (ll i = 0; i <= 200000; i++) furni_cnt[i] = 0;
    for (ll i = idx; i < M; i++) furni_cnt[furniture[i]]++;
    ll now = 0, cnt = K, multitap_idx = 0;
    while (now <= 200000)
    {
        if (cnt < furni_cnt[now]) //불가능하면
            return false;
        cnt -= furni_cnt[now];

        ll temp = 0;
        while (cnt > 0 && multitap_idx < N)
        {
            temp += multi[multitap_idx];
            cnt--; multitap_idx++;
        }

        if (cnt == 0) //다 채워졌다면
        {
            cnt = temp;
            now++;
        }
        else //남았다면 (멀티탭을 다 썼다면)
        {
            ll sum = 0;
            for (ll i = now + 1; i <= 200000; i++) sum += furni_cnt[i];

            if (sum <= cnt + temp) //가능
                return true;
            else //불가능
                return false;
        }
    }
    return true;
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll x, i;

    cin >> N >> K >> M;
    for (i = 0; i < N; i++)
    {
        cin >> x;
        multi.push_back(x);
    }
    for (i = 0; i < M; i++)
    {
        cin >> x;
        furniture.push_back(x);
    }
    sort(multi.begin(), multi.end(), greater<>());
    sort(furniture.begin(), furniture.end());

    ll s = 0, e = M - 1, mid, ans = 0;
    while (s <= e)
    {
        mid = (s + e) / 2;
        if (able(mid))
        {
            ans = M - mid;
            e = mid - 1;
        }
        else
        {
            s = mid + 1;
        }
    }

    cout << ans;
}

감사합니다.