백준 20654 "음료수는 사드세요 제발"

문제 : 음료수는 사드세요 제발

문제 링크
백준 20654 음료수는 사드세요 제발 풀이

사용 알고리즘: 병렬이분탐색(pbs), 그리디, 세그먼트 트리

문제 요약

N개의 액체가 있습니다.
각 액체는 3가지 속성이 있어요
1.맛
2.단위 가격 (원/리터)
3.최대 사용 가능 양 (리터)

음료수는 액체를 임의로 섞어 만들 수 있습니다.
음료수의 맛은 $min(섞인 액체들의 맛)$으로 정의됩니다. 

M개의 쿼리가 들어옵니다.
쿼리는 A,B 2개의 정수로 이루어집니다.
"A원 이하를 사용해 B리터 이상의 음료수를 만들 때, 맛의 최댓값을 구하시오. 조건을 만족하는 음료수를 만들 수 없다면 -1을 출력한다."

$1 <= N,M <= 10^5$

풀이

쿼리 하나에 대해서만 먼저 생각해봅시다.

'맛의 최댓값'을 구한다. 이런 류의 문제는 먼저 구하는 값에 대해 다음을 판별해 보는 것이 좋습니다.

" 어떤 값이 증가할 수록 어떤 조건을 만족할 가능성이 일관되게 증가/감소하는가? "

여기서는 '음료수에 섞인 액체들의 맛 중 최솟값'이 '어떤 값'입니다.
최솟값을 증가시켜 봅시다.
음료수에 섞을 수 있는 액체의 수가 점점 감소합니다.

사용할 수 있는 액체의 종류가 적어지면 가능한 조합이 점점 없어지므로 주어진 조건을 만족할 가능성이 항상 감소합니다.

따라서 우리는 음료수의 맛에 대해 이분탐색을 시행할 수 있습니다.

체커함수는 다음과 같습니다.
$Chk(X,A,B)$ :
어떤 값 X에 대해 X 이상의 맛을 가진 액체들로 주어진 조건을 만족하는 음료수를 만들 수 있는가?
"A원 이하를 사용하며 B리터 이상인 음료수"

이를 $O(N log N)$ 시간에 처리해봅시다.

1. 먼저 맛이 X 이상인 액체들을 모읍니다.
이제 다음 관찰에 의거하여 풀이를 만들어봅시다.

더 싼 음료수를 먼저 사용하는게 항상 이득이다.

2. 사용 가능한 액체들을 가격에 따라 정렬하고 순서대로 전부 음료수에 넣는다. 이때 음료수에 액체를 다 넣을 시 총 부피가 B 이상이 된다면 필요한 만큼만 더 사용한다. 이때 사용한 총 가격을 구해 A와 비교한다.

이렇게 O(N log N) 체커 함수를 만들었습니다.

쿼리 당 시간복잡도는 O(N*log N * log MAXVAL)이므로
총 시간복잡도는 O(M*N*log N*log MAXVAL)입니다.

이분탐색을 할 때 체커함수를 호출합니다. 이때 정렬/스위핑을 하면서 O(N log N)의 시간복잡도를 가지게 되는 것인데 M번 따로 호출하는게 아니라 한 번 호출 할 때 M개의 쿼리를 모두 처리하는 방식으로 효율을 비약적으로 개선시키는 알고리즘이 바로 병렬이분탐색입니다. 

병렬이분탐색을 최고로 잘 설명한 게시글이 다음 글입니다.
https://m.blog.naver.com/kks227/221410398513
병렬이분탐색을 배우실 계획이라면 꼭 위 글에서 배우시길 바랍니다.

1. 맛이 X 이상인 액체를 모으기. 본래라면 모을 때마다 O(N)이 걸리는 작업입니다.
이분탐색 전에 미리 카운팅 정렬처럼 맛이 K인 액체들끼리 모아놓읍시다.
마찬가지로 체커함수를 호출하기 전에 현재 mid가 K인 쿼리들끼리 모읍시다.
맛이 MAXVAL인 액체부터 1인 액체까지 하나씩 모으면 순서대로 쿼리를 갱신할 수 있습니다. 총 시간복잡도는 O(N * 갱신에 필요한 시간)입니다.

2. 액체를 이분탐색 전에 미리 가격에 따라 정렬해놓아 새로 인덱싱합시다.
"사용한 액체들을 순서대로 전부 음료수에 넣는다. 이때 음료수에 액체를 다 넣을 시 총 부피가 B 이상이 된다면 필요한 만큼만 더 사용한다. 이때 사용한 총 가격을 구해 A와 비교한다."
이 작업은 O(N)이 걸리므로 갱신 시간이 너무 큽니다. 액체들을 모으는 과정에서 액체의 인덱스가 섞이므로 스위핑 하는 것도 어렵습니다. 따라서 사용 가능한 액체들을 정렬해놓되, Prefix Sum을 빠르게 구하고, 이분탐색 또한 할 수 있는 자료구조가 필요합니다.

Prefix Sum에서 떠올리셔야 하는게 바로 세그먼트 트리입니다.
가격에 따른 인덱싱을 기준으로 세그먼트 트리에 각 액체의 사용가능량을 업데이트합니다.
그 후 루트에서부터 내려오면서 Prefix Sum의 lower bound를 O(log N)에 구할 수 있습니다.
B의 lower bound를 찾는다 -> 자신의 왼쪽 노드 구간이 합이 B 이상이면 왼쪽으로 내려가고, B 미만이면 "B - 왼쪽 노드 구간 합"에 대해 오른쪽으로 내려가는 재귀적인 방식으로 해결 가능, 리프 노드에 도달하면 종료.
이때 lower bound의 위치와 lower bound 값 모두 알 수 있으므로 B리터만큼의 음료수를 만들기 위한 최소 비용을 쉽게 구할 수 있습니다.

따라서 O(N log N + M) 시간에 모든 쿼리의 이분탐색 과정을 한 번 갱신시킬 수 있습니다.

총 시간복잡도는 $(O((N log N + M) log MAXVAL)$ 입니다.

코드

 

using ll = long long;
const int N = 1e5+5, inf = 1e9, mod = 1e9+7;
struct BIT{
    int n; ll*tree;
    BIT(int k){
        n = k;
        tree = new ll[n+1];
        clear();
    }
    void clear(){for(int i=0;i<=n;i++) tree[i]=0;}
    ~BIT(){delete[] tree;}
    void upd(int p,ll v){
        for(;p<=n;p+=p&-p) tree[p]+=v;
    }
    ll qry(int p){
        ll res = 0;
        for(;p>0;p-=p&-p)
            res += tree[p];
        return res;
    }
};
struct Seg{
    int st; ll*tree,sum;
    Seg(int k){
        st = 1<<int(ceil(log2(k)));
        tree = new ll[2*st];
        clear();
    }
    ~Seg(){delete[] tree;}
    void clear(){int i=0;i<=2*st;i++) tree[i]=0;}
    void upd(int p,ll v){
        for(tree[p+=st]+=v;p>1;p>>=1)
            tree[p>>1] = tree[p] + tree[p^1];
    }
    //returns the lower bound of K in segment tree prefix sum
    //val = { max(prefix sum) < K }
    int lb(ll K,ll&val){
        int id = 1;
        if(tree[id]<K) return -1;
        val = 0;
        while(id<st){
            ll Lval = tree[id<<1];
            if(Lval>=K) id=(id<<1);
            else id=(id<<1|1), K-=Lval, val+=Lval;
        }
        return id-st;
    }
};
struct Liquid{
    int d,p,l;
}A[N];
void solve(){
    int n,Q,M=0;
    cin>>n>>Q;
    for(int i=1;i<=n;i++){
        int d,p,l; cin>>d>>p>>l;
        A[i] = {d,p,l};
        M = max(M,d+1);
    }
    sort(A+1,A+n+1,[](auto&a,auto&b){
        return a.p<b.p;
    });
    vector<int> L[M];
    for(int i=1;i<=n;i++)
        L[A[i].d].pb(i);
    Seg f(n+1); BIT f2(n+1);
    vector<pair<ll,ll>> qry(Q);
    for(int i=0;i<Q;i++)
        cin>>qry[i].first>>qry[i].second;
    vector<int> lo(Q,0),hi(Q,M);
    // 최솟값이 lo 이하면 되고, hi 이상이면 안된다.
    while(true){
        int todo = 0,done = 0;
        vector<vector<int>> G; G.resize(M+1);
        for(int i=0;i<Q;i++){
            if(lo[i]+1<hi[i]){
                ++todo;
                G[lo[i]+hi[i]>>1].push_back(i);
            }
        }
        if(!todo) break;
        f.clear(); f2.clear();
        for(int i=M-1;i>=1;i--){
            for(int j:L[i]){
                f.upd(j,A[j].l);
                f2.upd(j,1LL*A[j].p*A[j].l);
            }
            for(int j:G[i]){
                ll g,l; tie(g,l) = qry[j];
                ll val;
                int id = f.lb(l,val);
                if(id==-1){hi[j]=i; continue;}
                ll cost = f2.qry(id-1) + (l-val)*A[id].p;
                if(cost <= g) lo[j] = i;
                else hi[j] = i;
            }
            done += G[i].size();
            if(todo == done) break;
        }
    }
    for(int ans:lo)
        cout<<(ans?ans:-1)<<'\n';
}