E. New Year and Three Musketeers

greedy, data structure

출처: Codeforces E. New Year and Three Musketeers

SOL)
multiset을 이용한다.
최적은 a, b, c가 각각 다른 범죄자를 처리하는 것이 최선이고
만약 이게 불가능하다면 최소의 비용으로
범죄자를 2명 또는 3명이 힘을 합쳐 잡는다.



[-] Collapse

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<climits>
#include<cmath>
using namespace std;
typedef long long ll;

#define y1 mine
#define mp make_pair

double pi = acos(-1);

vector<int> vec(3);
multiset<int> S;
multiset<int>::iterator it;
int n;

bool try3(int val){
    if (val > vec[2])
        return false;

    it = S.upper_bound(vec[1]);

    if (it == S.begin()) return false;
    else if (it != S.begin()) it--;

    int t1 = *it;

    S.erase(it);

    it = S.upper_bound(vec[0]);

    if (it == S.begin()){
        S.insert(t1);
        return false;
    }
    else{
        it--;
        S.erase(it);
    }

    return true;
}
void try2(int val){
    int thold = 0;
    if (val <= vec[0])
        thold = max(thold, vec[1] + vec[2]);
    if (val <= vec[1])
        thold = max(thold, vec[0] + vec[2]);
    if (val <= vec[2])
        thold = max(thold, vec[0] + vec[1]);
    if (val <= vec[0] + vec[1])
        thold = max(thold, vec[2]);
    if (val <= vec[0] + vec[2])
        thold = max(thold, vec[1]);
    if (val <= vec[1] + vec[2])
        thold = max(thold, vec[0]);


    it = S.upper_bound(thold);
    if (it != S.begin()) {
        it--;
        S.erase(it);
    }
    return;
}

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d", &n);

    for (int i = 0; i < 3; i++){
        scanf("%d", &vec[i]);
    }

    sort(vec.begin(), vec.end());

    for (int i = 0; i < n; i++){
        int v; scanf("%d", &v);
        S.insert(v);
        if (v > vec[0] + vec[1] + vec[2]){
            printf("%d", -1);
            return 0;
        }
    }

    int ans = 0;

    while (!S.empty()){
        ans++;
        it = S.end();
        it--;
        int val = *it;
        S.erase(it);

        bool isCan = try3(val);

        if (isCan) continue;
        else try2(val);
    }

    printf("%d", ans);
    return 0;
}