Bài toán D: Lễ kỷ niệm trưởng thành

Phân tích: Mỗi cá nhân sẽ nhận được ngọc từ những người phía trước và đồng thời cung cấp ngọc cho những người phía sau. Công thức tính trạng thái cuối cùng: số ngọc cuối = (số người đang có ngọc khi đến lượt i) + (n - i). Trong đó:

• (n - i): Số ngọc phải chuyển cho những người phía sau
• số người đang có ngọc: Được duy trì bằng hàng đợi ưu tiên để theo dõi thời điểm các ngọc trở về 0

Triển khai thuật toán:

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;

void process() {
    ll n;
    cin >> n;
    vector<ll> input(n + 1), result(n + 1);
    
    for (ll i = 1; i <= n; i++) 
        cin >> input[i];
    
    ll activeCount = 0;
    priority_queue<ll, vector<ll>, greater<ll>> expiration;
    
    for (ll i = 1; i <= n; i++) {
        while (!expiration.empty() && expiration.top() == i) {
            activeCount--;
            expiration.pop();
        }
        
        ll current = input[i];
        current -= (n - i);  // Trừ phần phải chuyển cho người sau
        
        if (current < 0) 
            current = 0;
        
        current += activeCount;  // Cộng phần nhận từ người trước
        expiration.push(current + i);
        activeCount++;
        
        result[i] = current;
    }
    
    for (ll i = 1; i <= n; i++)
        cout << result[i] << " ";
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    process();
    return 0;
}

Bài toán E: Chia bánh đồng thời

Phương pháp: Sử dụng tìm kiếm nhị phân để xác định số phần tối đa k sao cho với mỗi phần nhỏ thứ i, tồn tại phần lớn thứ j thỏa mãn 2*a[i] <= a[j]. Với dãy đã sắp xếp tăng dần, ta kiểm tra bằng kỹ thuật hai con trỏ:

• Phần nhỏ thứ i sẽ tương ứng với phần lớn thứ n - k + i
• Nếu 2*a[i] > a[n - k + i] với bất kỳ i nào → k không hợp lệ

Cài đặt chi tiết:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

bool validatePortion(ll k, const vector<ll>& cakes, ll n) {
    for (ll i = 0; i < k; i++) {
        if (2 * cakes[i] > cakes[n - k + i])
            return false;
    }
    return true;
}

void solve() {
    ll n;
    cin >> n;
    vector<ll> cakes(n);
    
    for (ll i = 0; i < n; i++)
        cin >> cakes[i];
    
    sort(cakes.begin(), cakes.end());
    
    ll left = 0, right = n / 2, maxValid = 0;
    while (left <= right) {
        ll mid = (left + right) / 2;
        if (validatePortion(mid, cakes, n)) {
            maxValid = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    cout << maxValid << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}