[SWEA] 8998 세운이는 내일 할거야

 

이분탐색을 통해 풀 수 있는 문제다

X일을 mid로 설정해보자

 

그 후 정렬을 하고 mid값으로 설정했을 때 숙제를 할 수 있는지 하나하나 확인해보자!

시간이 좀 걸린다..!

 

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
#define ll long long
const int MAXN = 1e6 + 5;
int N;
pair<ll, ll> arr[MAXN];
 
bool solve(ll mid) {
    ll now = mid-1;
    for (int i = 0; i < N; i++) {
        ll day = arr[i].first;
        ll time = arr[i].second;
        now += time;
        if (now > day) return false;
    }
    return true;
}
 
int main() {
    //freopen("input.txt", "r", stdin);
    int tcase; scanf(" %d", &tcase); int c = 1;
    while (tcase--) {
        scanf(" %d", &N);
        for (int i = 0; i < N; i++) scanf(" %lld %lld", &arr[i].second, &arr[i].first);
        sort(arr, arr+N);
 
        ll l = 0, r = 1e18, ans = 0;
        while (l <= r) {
            ll mid = (l + r) / 2;
            if (solve(mid+1)) {
                ans = max(ans, mid);
                l = mid + 1;
            }
            else r = mid - 1;
        }
        printf("#%d %lld\n", c++, ans);
    }
}