[백준] 17503 맥주 축제

도수를 mid값으로 생각해보자

최대 32번 봐야하고 볼때마다 NlogN연산을 한다고 생각해보자

mid값까지의 도수 중 선호도가 높은 N개를 정해보는 것이다

이분탐색을 통해 찾으면 되지만 오래걸린다!

다른사람들은 pq를 통해 풀었는데 그럼 빠르다..!!

 

소스코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define ll long long
ll n,m,k;
vector<pair<ll,ll>> vt;
bool check(ll mid){
    vector<ll> temp;
    for(int i=0;i<k;i++){
        if(vt[i].first <= mid) temp.push_back(vt[i].second);
        else break;
    }
    if(temp.size()<n) return false;
 
    sort(temp.rbegin(),temp.rend());
    ll ret=0;
    for(int i=0;i<n;i++) ret+=temp[i];
    return (ret>=m);
}
int main(){
    scanf(" %lld %lld %lld",&n,&m,&k);
    for(int i=0;i<k;i++) {
        ll a,b; scanf(" %lld %lld",&a,&b);
        vt.push_back({b,a});
    }
    sort(vt.begin(),vt.end());
    ll s=1,e=1e13,ans= 1e13;
    while(s<=e){
        ll mid = (s+e)/2;
        if(check(mid)){
            ans = min(ans,mid);
            e = mid-1;
        }
        else s = mid+1;
    }
    if(ans==1e13) puts("-1");
    else printf("%lld\n",ans);
}

 

그럼 pq를 통해 푸는 방법을 살펴보자

k개를 돌아보며 하나씩 선호도값을 더해보자

이 때 pq에도 같이 넣어준다

만약 pq가 내가 정한 술이라 할 때

pq의 사이즈가 n보다 커지면 가장 선호도가 낮은걸 빼주자

그리고 pq의 사이즈가 n이고 sum>=m으로 문제의 조건을 만족한다면

내가 마지막으로 넣어준 도수를 출력해주자

k번동안 못찾으면 답은 없다 => -1

 

소스코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
ll n,m,k,sum;
 
int main(){
    scanf(" %lld %lld %lld",&n,&m,&k);
    vector<pair<ll,ll>> vt(k);
    for(int i=0;i<k;i++) scanf(" %lld %lld",&vt[i].second,&vt[i].first);
    sort(vt.begin(),vt.end());
    priority_queue<ll> pq;
    for(int i=0;i<k;i++){
        pq.push(-vt[i].second);
        sum+=vt[i].second;
 
        if(pq.size()>n){
            sum +=pq.top();
            pq.pop();
        }
 
        if(pq.size()==n && sum >=m){
            printf("%lld\n",vt[i].first); return 0;
        }
    }
    puts("-1");
}