CutSticks

문제

아무 막대를 선택해서 임의의 정수길이 2개로 자른다

최대 C 번 절단 할수 있으며,
자른 막대는 다음 막대를 절단할때 사용이 가능하다

막대 절단을 완료하였을때 내림차순 정렬 기준으로 sticks[K] 의 최대값을 리턴

C : 1 ~ 1억
sticks[] : 1~50개의 int, 각 int 는 1 ~ 1억까지 가능
K : 1 ~ C + sticks.size()

이때, 리턴값의 절대오차 or 상대오차는 1e-9 미만

예시 입력

1)
{5, 8},
1, 
1

2)
{5, 8},
1,
2

3)
{5, 8},
1,
3

4)
{1000000000, 1000000000, 1},
2,
5

5)
{76, 594, 17, 6984, 26, 57, 9, 876, 5816, 73, 969, 527, 49},
789,
459

예시 출력

8
5
4
1
34.92

생각의 변화

200 160 100 80 60 20 10
C=8

K번째 최대
-> '길이 40 이상인 막대는 몇개' 로 문제를 변경

200 160 100 80 60
5   4   2   2  1 = 14

절단횟수
4   3   1   1  0 = 9

절단가능한 횟수가 9이므로
만들수 있는 막대는 14-(9-8) = 13

따라서
K가 13이하일 경우 K최대값은 40이하
K가 14이상일 경우 K최대값은 40미만

0~10억 이분탐색

midstick < K
midstick >= K

cut 횟수를 저장하거나, 내림차순 정렬을 할 필요없이
min 값을 그대로 리턴해도 된다

/ 할때 long long 을 쓰지 않으면 1/3.3억 계산이 되면서
비교연산이 정상적으로 동작하지 않을수 있다

midstick 갯수는 += (stick/mid) 로 구할수 있지만
자르기전 유효한 막대 갯수 + C 가 될수도 있다

min 과 max 어떤 값을 리턴해도 괜찮다.

pseudo code

maxKth(sticks, C, K)
    min = 0.0
    max = 1000000000.0
    
    mid
    
    midstick
    initial_valid_stick
    
    while max-min > 1e-9  &&  max-min/max > 1e-9
        mid = (min + max) / 2
        
        midstick = 0
        initial_valid_stick = 0
        
        for (i=0  i<sticks.size()  i++)
            stick = sticks[i]
            
            if ((stick / mid) > 0)
                initial_valid_stick++
                midstick += (stick / mid)
                
        limit = initial_valid_stick + C
        midstick = std::min(midstick, limit)
        
        if (midstick < K)
            max = mid
        else
            min = mid
            
    return min

while loop 없이 하는 법에 대해

while loop 을 돌리지 않고 100회 정도 돌리는 방식도 존재한다

class CutSticks
{
public:
    explicit CutSticks() {}

    double maxKth(vector<int> sticks, int C, int K)
    {
        
        double low = 0;
        double high = 1e9;

        int i, j;

        for (i = 0; i < 100; i++)
        {
            long long count = 0;

            double mid = (low + high) / 2;

            long long cut = 0;

            for (j = 0; j < sticks.size(); j++)
            {
                long long next = (long)(sticks[j] / mid);

                cut += max<double>(0.0, (next - 1));

                count += next;
            }

            count -= max<double>(0.0, cut - C);

            if (count >= K)
                low = mid;
            else
                high = mid;
        }
        
        return low;
    }
};