[토요라운드] E. 풍선 공장 (15810)

세상 사람들에게 파라메트릭 서치를 풀었다고 자랑하고 싶다..

 

 

보니깐 시간을 기준으로 풀면 되겠다 싶었다. 시간이 주어졌을 때 개수는 구할 수 있으니깐

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#pragma warning(disable:4996)
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

i64 calc(i64 mid, int n, vector<int> a)
{
    i64 sum = 0;
    
    for (int i = 0; i < n; i++)
    {
        sum += mid / a[i];
    }
    
    return sum;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
        
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    
    i64 hi = 1000000000000;
    i64 lo = 1;
    
    for (int i = 0; i < 42; i++)
    {
        i64 mid = (hi + lo) / 2;
        
        if (calc(mid, n, a) < m)
            lo = mid;
        else
            hi = mid;
    }
    
    printf("%lld\n", hi);
    
    return 0;
}

 

지금 생각해보니 while문 조건으로 hi, lo 설정하면 됐을 것 같은데 실수 범위의 이분탐색을 많이했어서 저렇게 짰음

 

 

40번 돌리면 10^6 범위로 오차를 줄일 수 있습니다