백준 14575번 뒤풀이 [C++]

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

 

 

#문제 간단 정리

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

#문제 해결 방법

 

우선 첫번째로 모든 최소값 Li 를 더해서

T를 넘으면 불가능이고

모든 최대값 Ri  을 더해서 

T 보다 낮으면 T를 만들 수 없어서 불가능이다

 

그 외에는 s값을 이분탐색으로 구해서

Li 만큼 우선 주고 mid 나 R[i] 값중 둘중 

R[i] 이 mid 보다 크다면

 

mid - L[i] 으로 

여유분으로 줄 수 있는 값을 구할 수 있다.

 

우선 최소값 + 여유분이 >= t 라면 무조건 t를 만들 수 있기 때문에

이걸 조건으로 사용한다

 

#전체 코드

#include <iostream>
#include <climits>
#include <vector>
using namespace std;

typedef long long ll;

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

    int n, t;
    cin >> n >> t;

    vector<int> L(n);
    vector<int> R(n);


    ll sumL = 0, sumR = 0;
    ll maxL = 0;  
    for (int i = 0; i < n; i++) {
        cin >> L[i] >> R[i];
        sumL += L[i];
        sumR += R[i];
        if (L[i] > maxL) maxL = L[i];
    }

    if (sumL > t || sumR < t) {
        cout << -1 << '\n';
        return 0;
    }

    int l = 0, r = 1e9;

    int mid;
    int ans;
    while (l <= r) {

        mid = (r + l) / 2;

        bool possible = true;
        int sum = 0; //최소로 필요한 맥주량
        int dum = 0; //더 줄수 있는 맥주량
        for (int i = 0; i < n; i++) {
            if (L[i] > mid) {
                possible = false;
                break;
            }
            sum += L[i];
            if (R[i] < mid) {
                dum += R[i] - L[i];
            }
            else {
                dum += mid - L[i];
            }

        }

 

        if (sum + dum >= t && possible) {
            ans = mid;
            r = mid - 1; 
        }
        else {
            l = mid + 1;
        }
    }
    
    cout << ans;

    return 0;
}