C 문제: 과자 쌍 찾기

각 과자에 대해 크기의 두 배 이상인 과자를 이진 탐색으로 찾아, 이 과자와 쌍을 이룰 수 있는 과자의 수를 계산합니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    int n;
    cin >> n;
    vector<int> desserts(n);
    
    for (int i = 0; i < n; ++i) {
        cin >> desserts[i];
    }
    
    sort(desserts.begin(), desserts.end());
    
    ll pairs = 0;
    
    for (int i = 0; i < n; ++i) {
        int target = desserts[i] * 2;
        auto it = lower_bound(desserts.begin(), desserts.end(), target);
        pairs += (desserts.end() - it);
    }
    
    cout << pairs << endl;
    return 0;
}

D 문제: 돌 분배 문제

각 사람이 성년이 될 때 가지고 있는 돌의 수를 계산합니다. 차이 배열(difference array)을 사용하여 구간 업데이트를 효율적으로 처리합니다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> stones(n);
    vector<int> diff(n + 2, 0);
    
    for (int i = 0; i < n; ++i) {
        cin >> stones[i];
        diff[i] = stones[i] - (i > 0 ? stones[i-1] : 0);
    }
    
    for (int i = 0; i < n; ++i) {
        stones[i] = diff[i] + (i > 0 ? stones[i-1] : 0);
        diff[i] += (i > 0 ? diff[i-1] : 0);
        
        int transfer = min(stones[i], n - i - 1);
        diff[i+1]++;
        diff[i+transfer+1]--;
        stones[i] -= transfer;
    }
    
    for (int i = 0; i < n; ++i) {
        cout << stones[i] << " ";
    }
    cout << endl;
    
    return 0;
}

E 문제: 쌍 이루기 문제

이진 탐색을 사용하여 배열의 앞부분과 뒷부분에서 각각 x개의 원소를 선택하여 쌍을 이룰 수 있는 최대 x를 찾습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool canPair(const vector<int>& arr, int x) {
    for (int i = 0, j = arr.size() - x; i < x; ++i, ++j) {
        if (arr[i] * 2 > arr[j]) {
            return false;
        }
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    vector<int> values(n);
    
    for (int i = 0; i < n; ++i) {
        cin >> values[i];
    }
    
    sort(values.begin(), values.end());
    
    int left = 0, right = n / 2;
    int result = 0;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        if (canPair(values, mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    cout << result << endl;
    return 0;
}