[17503] 맥주 축제

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

17503번: 맥주 축제

<문제>

이분탐색으로 탐색 횟수를 log2(2^31) == 31번정도로 만들 수 있고,

하나의 탐색당 O(KlogK)정도만에 먹을 수 있는 맥주의 선호도 합을 구할 수 있다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, k;
vector<pair<ll, ll>> v;
bool getScore(ll mx) {
    ll ret = 0, cnt = 0;
    vector<ll> sc;
    for (int i = 0; i < k; i++)
        if (v[i].second <= mx) sc.push_back(v[i].first);
    if (sc.size() < n) return false;
    sort(sc.begin(), sc.end(), greater<ll>());
    for (int i = 0; i < n; i++) ret += sc[i];
    return ret >= m;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    v.resize(k);
    int i;
    ll l = 1, r = 1e10, ans = 1e10;
    for (i = 0; i < k; i++) cin >> v[i].first >> v[i].second;
    while (l <= r) {
        ll mid = (l + r) / 2;
        bool flag = getScore(mid);
        if (flag) {
            r = mid - 1;
            ans = min(mid, ans);
        } else
            l = mid + 1;
    }
    if (ans == 1e10) ans = -1;
    cout << ans;
    return 0;
}