BOJ 12945 재미있는 박스 정리

재미있는 박스 정리
(http://boj.kr/12945)

이 문제도 매우 오래 고민했다.
일단 오름차순으로 정렬한다. 그 뒤에 작은 것부터 차례대로 보는데,
현재 알아야하는 정보는 두 가지다.
하나는 현재 상자가 넣을 수 있는 상자 개수이고, 하나는 이전의 상자 중에서 다른 상자에 넣을 수 있는 상자의 최댓값이다.
그럼 최댓값 * 2만큼은 이미 정해진 상자이다.
정해진 상자에서 다른 상자에 들어가는 상자는 작을 수록 좋다. (다른 상자를 넣을 필요가 없으니까) 그리고 다른 상자를 넣는 상자는 클 수록 좋다. (현재 상자가 작은 상자를 넣을 수도 있으니까)
그러니 두 개를 고려해서 현재 상자가 넣을만한 상자가 남았는지를 보면 된다.

생각해보니 이분탐색으로도 될 것 같다.

#include <bits/stdc++.h>
 
using namespace std;
 
int arr[500000];
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0;i < n;++i)
        scanf("%d", &arr[i]);
    sort(arr, arr + n);
 
    int cnt = 0;
    for (int i = 0, j = -1;i < n;++i) {
        while (arr[j + 1] * 2 <= arr[i]) 
            j++;
 
        if (cnt + max(j - (i - cnt) + 1, 0) < j + 1) 
            cnt++;
    }
 
    printf("%d", n - cnt);
 
    return 0;
}