[백준] 28493 - Burgers (c++)

NOI 2023 Qualification 4번 문제이다.

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

 

한줄평

진짜 어려운 문제였다. 매개 변수 탐색을 연습할 필요가 있다고 느꼈다.

 

문제 요약

N가지의 재료가 있다. A버거와 B버거가 있고 각각 들어가는 재료가 다르다. 버거의 갯수를 최대로 만들어라.

 

풀이 (log10^9*N)

• 매개 변수 탐색

만들 버거의 개수를 기준으로 매개 변수 탐색을 하면 된다. 각 개수에 대해 재료를 순회하며 A버거를 만들 수 있는 최소,최대 개수를 갱신하면 그 개수가 가능한지 불가능한지 알 수 있다. (A버거를 만들 수 있는 개수의 교집합이 있으면 가능, 없으면 불가능)

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;cin>>n;
    ll x[n],a[n],b[n];
    for(ll &i:x)cin>>i;
    for(ll &i:a)cin>>i;
    for(ll &i:b)cin>>i;

    int l=0,r=1e9;
    while(l<=r) {
        int mid =(l+r)/2;
        ll amn=0,amx=1e9;
        bool can =1;
        for(int i=0;i<n;i++) {
            if(a[i] == b[i]) {
                if(x[i]/a[i] < mid) can = 0;
            }
            else if(a[i]<b[i]) {    
                if(a[i]*mid>x[i]) can=0;
                if(b[i]*mid>x[i])
                    amn=max(amn,mid-(x[i] -a[i]*mid) /(b[i] -a[i]));
            }
            else {
                if(b[i]*mid>x[i]) can=0;
                if(a[i]*mid>x[i])
                    amx=min(amx,(x[i]-b[i]*mid)/(a[i]-b[i]));
            }
        }
        if(can&&amn<=amx)
            l=mid+1;
        else
            r=mid-1;
    }
    cout<< r;
}