[TopCoder] CutSticks (막대들 자르기)

존은 다양한 길이의 막대기를 가지고 있다. 각 요소가 하나의 막대의 길이인 막대가 주어집니다.

그는 C번의 컷을 수행한다. 각각의 컷에서, 그는 그의 스틱 중 하나를 선택하고 그것을 임의의 양의 길이를 가진 정확히 두 개의 스틱으로 나눈다. 그 다음에 컷을 할 때 각각의 스틱을 다시 선택할 수 있습니다.

컷을 모두 소화한 뒤 길이순으로 스틱을 분류해 K번째(1-based) 스틱을 선택한다. 선택한 스틱의 최대 길이를 반환합니다. K개 이상의 스틱으로 끝나려면 최소한 필요한 만큼의 컷을 수행해야 합니다.

Definition

Class:

 

CutSticks

Method:

 

maxKth

Parameters:

 

vector <int>, int, int

Returns:

 

double

Method signature:

 

double maxKth(vector <int> sticks, int C, int K)

Examples

0)

{5, 8}

1

1

Returns: 8.0

John can make at most one cut. He should either cut the stick of length 5 (it doesn't matter where) or not make any cuts at all. If he makes no cuts, then after he sorts the sticks, they will be in the following order: {8, 5}. He chooses the 1st stick, which has length 8.

1)

{5, 8}

1

2

Returns: 5.0

Again, the easiest thing to do here is not make any cuts.

2)

{5, 8}

1

3

Returns: 4.0

John has 2 sticks and he can make at most one cut. In this case, since K is 3, he is required to make a cut so he can end up with 3 sticks. He should cut the longest stick into two equal sticks of length 4. After he sorts the sticks, they will be in the following order: {5, 4, 4}. He will choose the 3rd stick, which has length 4.

3)

{1000000000, 1000000000, 1}

2

5

Returns: 1.0

4)

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

789

456

Returns: 34.92

 

Notes

- Your return value must have an absolute or relative error less than 1e-9.

---

Your return value must have an absolute or relative error less than 1e-9.

 

→ 이분 탐색 문제이다. 

 

각각 길이가 다른 막대들이 여러개가 있고, 임의의 막대를 선택하여 C번의 Cut을 수행한 후에 

 

길이 내림차순으로 정렬한 후 K번째의 막대를 선택했을 때 가장 최대값이 나올 수 있도록 한다. 

 

example 1을 살펴보자. 

 

{5, 8}

C: 1

 

K : 2

 

막대 길이가 각각 5, 8이고 1번의 Cut 수행이 가능하다. 그러고 나서 2번째로 긴 막대의 길이를 반환한다.

 

먼저 1번의 Cut을 수행하지 않을 경우, 8, 5 순이므로 5가 반환된다.

 

그럼 Cut을 수행하게되면 8, 5 중 5을 Cut하게 되면 더 작은 값을 반환할 수 밖에 없다. 

 

8을 두동강 내야하는데, 5보다 작은 수들(4, 4)로 하게되면 4를 반환하기 때문에 안되고, 

 

해봐야 6, 2 (6, 5, 2)로 하든 5, 3 (5, 5, 3)으로 하든 결국에 5가 반환된다. 

 

여기서 문제를 푸는 중요한 핵심 키를 얻을 수 있다. 

 

가장 긴 K번째 막대의 길이를 반환하기 위해서는 특정 길이 X인 막대를 K개 만들어 주어야한다.

 

 

이 길이 X가 무엇인지에 대해서는 이분탐색으로 찾아야한다. 

 

 

#include <vector>
#include <algorithm>
using namespace std;

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

이분 탐색을 위한 변수들을 선언한다. 

 

        for(int i=0; i<100; i++){
            long long count = 0;
            mid = (low + high)/2;
            long long cut = 0;
            for(int j=0; j<sticks.size(); j++){
                long long pieceNum = (long)(sticks[j]/mid);
                cut += max((long long)0, (pieceNum-1)); //1개도 못 만드는 경우 있으므로
                count += pieceNum;
            }

오차를 줄이기 위한 충분한 반복횟수로 100번을 돌리는 것으로 하고, 

 

막대들 배열을 순회하면서 만들어지는 특정 길이 X의 토막 개수를 누적한다. 

 

절단 내는 개수(만들어진 토막 개수-1), 토막 개수를 각각 누적해준다. 

 

            count -= max((long long)0, (cut-C));

일단 잘랐는데, 실제로 Cut할수 있는 횟수보다 큰 횟수를 잘랐을 경우 넘어선 만큼 토막 개수에서 빼준다.

 

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

만들어진 전체 토막개수 count가 K보다 크다는 것은, 토막의 길이를 좀 더 키워도 된다는 소리이다. 

 

        return mid;

반복문 탈출 시 mid를 반환한다.