[CodeForces - 604B] More Cowbell

난이도: 1400

 

태그

• Binary Search
• Parametric Search
• Greedy

 

풀이

1. 크기 \( s \)를 고정시켜볼까?

크기 \( s \)를 증가시킬수록, 필요한 상자의 개수는 비증가합니다.

// 크기가 늘어나도, 동일한 배치를 유지하면 필요한 상자 수를 그대로 유지할 수 있기 때문이죠.

 

즉, \( k \)개 이하가 필요한 위치를 파라메트릭 서치 + 이진 탐색으로 찾아볼 수 있습니다.

 

2. 크기 \( s \)를 고정시켰을 때, 필요한 상자의 개수는?

남은 물건들 \( s_1, s_2, \ldots, s_N \)을 상자에 담는 방식을 생각해봅시다.

 

이 때, \( s_N \)이 담기는 상자를 자세히 봅시다.

\( s_N \)이 담긴 상자에 남은 공간은 \( s - s_N \)이 됩니다. 이 남은 공간은 어떻게 해야 할까요?

 

그 남은 공간에 들어갈 수 있는 가장 큰 물건을 찾아 넣어주면 됩니다.

없으면 아무것도 안 넣으면 되고요.

// 더 작은 물건을 넣으면요? or 물건을 안 넣으면요?

// 각 경우에 대해 남은 상자들에 넣어야 하는 물건들을 크기 순으로 정렬해봅시다.

// 물건을 안 넣으면, (넣은 뒤 남은 물건들) ⊂ (안 넣을 때 남은 물건들)이므로 최적이 아닙니다.

// 더 작은 물건을 넣으면, (큰 걸 넣은 뒤 남은 물건들 중 i번째) ≤ (작은 걸 넣은 뒤의 i번째)이므로 최적이 아닙니다.

 

그 뒤는요? 남은 물건들로 똑같은 문제 풀어주면 됩니다.

 

3. 코드

int arr[100020];
 
void Main(){
    int n, k; cin >> n >> k;
    int mx = 0;
    for (int i = 1; i <= n; i++){ cin >> arr[i]; mx = max(mx, arr[i]); }
    int st = mx, ed = 2000000, ans = 2000000; while (st <= ed){
        int mid = st+ed >> 1;
        multiset<int> s;
        for (int i = 1; i <= n; i++){ s.insert(arr[i]); }
        int res = 0; while (!s.empty()){
            res += 1;
            auto it = s.end(); --it; int x = *it; s.erase(it);
            auto jt = s.upper_bound(mid-x);
            if (jt == s.begin()){ continue; } --jt;
            s.erase(jt);
        }
        if (res <= k){ ed = mid-1; ans = mid; } else{ st = mid+1; }
    }
    cout << ans;
}