Edu82(Div.2) B. National Project

이분탐색으로 해결할 수 있는 문제다

mid일만큼 본다고 하면 mid/(g+b)만큼 g or b를 볼 수 있다

그럼 g*(mid/(g+b))만큼 좋은 날을 볼 수 있고 그 다음 볼수있는 날도 최대 g만큼 좋은날이다

결국 답은 g*(mid/(g+b))+min(mid/(g+b),g)로 나온다!!

근데 문제를 잘 보면 전체 도로를 어쨌든 공사는 해야하므로 최소 n일은 봐야한다

 

 

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
 
#define ll long long
ll n, g, b;
 
bool solve(ll mid) {
    ll len = (n + 1) / 2;
    ll cnt = mid / (g + b);
    ll res = mid % (g + b);
    ll gcnt = g * cnt + min(g, res);
    return (gcnt >= len);
}
 
int main() {
    int t; scanf(" %d", &t);
    while (t--) {
        scanf(" %lld %lld %lld", &n, &g, &b);
 
        ll l = 0, r = 1e18;
        ll ans = 1e18;
        while (l <= r) {
            ll mid = (l + r) / 2;
            if (solve(mid)) {
                ans = min(ans, mid);
                r = mid - 1;
            }
            else l = mid + 1;
        }
        
        printf("%lld\n", (ans<=n) ? n :ans);
    }
}