1166 선물

입력값이 10억이라서 음! 선형탐색도 무리겠고 이분탐색을 써야겠다고 생각이 들었음

 

그래서 a의 길이를 이분탐색으로 구하려고 했다

 

하지만 틀렸음ㅋㅋㅋ check 함수 구현할 때 살짝 예상했었긴 한데 이게 부피로 계산하는 거여서 살짝 찜찜하긴 했었다.

 

원인은 이 부분이 맞았다. 아 그래서 a > l || a > w || a > h 도 넣었는데 소용없었구나 (그렇겠지)

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

double n, l, w, h;

bool check(double mid)
{
    if (mid * mid * mid * n > l * w * h)
        return false;
    if (mid > l || mid > w || mid > h)
        return false;
    return true;
}

int main()
{
    cin >> n >> l >> w >> h;

    double lo = 0;
    double hi = 1000000000;

    for (int i = 0; i < 100; i++)
    {
        double mid = (lo + hi) * 0.5;

        if (check(mid))
            lo = mid;
        else
            hi = mid;
    }

    printf("%.10lf\n", lo);


    return 0;
}

 

그래서 이걸 n 개수를 이용해서 비교해준다! 

 

a가 고정되면 l, m, h에 들어갈 수 있는 상자 개수가 나오므로 개수랑 n이랑 비교해주면 된다.

 

이분탐색은 저 비교하는 기준 잡는게 어렵단 말이지

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

double n, l, w, h;

bool check(double mid)
{
    if (floor(l / mid) * floor(w / mid) * floor(h / mid) < n)
        return false;
    return true;
}

int main()
{
    cin >> n >> l >> w >> h;

    double lo = 0;
    double hi = 1000000000;

    for (int i = 0; i < 100; i++)
    {
        double mid = (lo + hi) * 0.5;

        if (check(mid))
            lo = mid;
        else
            hi = mid;
    }

    printf("%.10lf\n", lo);


    return 0;
}