백준 24041번 성싶당 밀키트 [C++]

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

 

 

#문제 간단 정리

이분탐색(매개변수 탐색)

 

#문제 해결 방법

 

범위 관리를 잘 해줘야 되는 문제 같다

 

우선 x가 범위가 매우 넓으니  

매개변수 탐색으로 logn 을 사용하고

 

각각 세균의 개수를 확인하면 O(n) 인데

정렬을 한 후에 최대 k개를 총합에서 제거한다고 생각하면

n log n 이라

 

이분탐색 + 정렬이라

log n * nlogn 정도로 생각 할 수 있는데

 

세균의 범위는 대략 2e9 (20억 정도)

각 n의 s*max(1,x-L) 합 <=G 인데

최악의 경우 N=1 G=1e9 , S:1, L 1e9로

S * max(1, x - L) <= G
1 * (x - 1e9) <= 1e9
x - 1e9 <= 1e9
x <= 2e9

x의 범위는 2e9이다

 

n의 범위는 20만이니 시간복잡도는 충분하다

 

 

#전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;

typedef long long ll;
const ll maxDay = 20000000000;

int n, k;
ll g;

vector<tuple<int, int, int>> ingre;


bool possible(int x) {
    vector<ll> gs; //o ==1 중요하지 않은 재료
    ll gsum = 0;

    for (auto& t : ingre) {
        int s, l, o;
        tie(s, l, o) = t;  // 튜플 분해
        ll tempG = (ll)s * max(1, x - l);
        gsum += tempG;
        if (o == 1) {
            gs.push_back(tempG);
        }
    }

    sort(gs.begin(), gs.end(), greater<>());

    for (int i = 0; i < min((int)gs.size(), k); i++) {
        gsum -= gs[i];
    }

    if (gsum <= g) {
        return true;
    }
    else return false;
}



int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> g >> k;

    ingre.resize(n);

    for (int i = 0; i < n; i++) {
        int s, l, o;

        cin >> s >> l >> o;
        ingre[i] = make_tuple(s, l, o);
    }

    ll l = 1, r = maxDay;
    int ans = 0;

    while (l <= r) {
        ll mid = (l + r) / 2;

        if (possible(mid)) {
            l = mid + 1;
            ans = mid;
        }
        else {
            r = mid - 1;
        }


    }

    cout << ans << '\n';

    return 0;
}