Hiểu bài toán

Cho ~N~ món quà (~N~ chẵn). Mỗi món quà có hai giá trị ~a_i~ và ~b_i~ là mức độ hạnh phúc của hai anh em Téo và Tỳ. Cần chia đều ~N/2~ món cho mỗi người để tổng hạnh phúc (tổng a của người này + tổng b của người kia) là lớn nhất.

Gọi tập quà Téo nhận là ~S~, tập Tỳ nhận là ~S^c~. Khi đó tổng hạnh phúc là: $$ \sum_{i \in S} a_i + \sum_{i \notin S} b_i = \sum_{i=1}^{N} b_i + \sum_{i \in S} (a_i - b_i) $$ Để tối ưu, ta cần chọn ~N/2~ món quà có chênh lệch ~(a_i - b_i)~ lớn nhất để cho vào tập ~S~ (cho Téo).

Các cách tiếp cận

Cách Sắp xếp chênh lệch (Greedy)

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    int N;
    cin >> N;
    vector<pair<int, int>> gifts(N);
    ll sumB = 0;
    for (int i = 0; i < N; ++i) {
        cin >> gifts[i].first >> gifts[i].second;
        sumB += gifts[i].second;
    }
    // Sap xep giam dan theo (a - b)
    sort(gifts.begin(), gifts.end(), [](const pair<int, int>& x, const pair<int, int>& y) {
        return (x.first - x.second) > (y.first - y.second);
    });
    ll ans = sumB;
    for (int i = 0; i < N / 2; ++i) {
        ans += (gifts[i].first - gifts[i].second);
    }
    cout << ans << endl;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Đây là cách tiếp cận trực quan nhất và là tối ưu cho ràng buộc ~N \le 500,000~.

1. Tính tổng sumB của tất cả các giá trị ~b_i~.
2. Sắp xếp các món quà theo giá trị chênh lệch ~(a_i - b_i)~ giảm dần.
3. Chọn ~N/2~ món quà đầu tiên (có chênh lệch lớn nhất) cho Téo, cộng chênh lệch vào sumB.
4. Kết quả là sumB sau khi cộng các chênh lệch.

Độ phức tạp là ~O(N log N)~ do sắp xếp, hoàn toàn chấp nhận được với ~N = 500,000~.

Cách Tối ưu hóa với Vét Cạn (chỉ hiệu quả với N nhỏ)

// Pseudocode cho cách tiếp cận DP/Knapsack
// Chỉ chạy được nếu N rất nhỏ (ví dụ <= 20)
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int N;
int a[25], b[25];
int memo[25][13];

int solve(int idx, int chosen) {
    if (chosen > N/2) return -1e9;
    if (idx == N) return (chosen == N/2) ? 0 : -1e9;
    if (memo[idx][chosen] != -1) return memo[idx][chosen];
    // Chọn món này cho Téo (lấy a)
    int take = a[idx] + solve(idx + 1, chosen + 1);
    // Không chọn (để cho Tỳ, lấy b)
    int skip = b[idx] + solve(idx + 1, chosen);
    return memo[idx][chosen] = max(take, skip);
}

int main() {
    cin >> N;
    for(int i=0; i<N; i++) cin >> a[i] >> b[i];
    memset(memo, -1, sizeof(memo));
    cout << solve(0, 0);
}

• Time Complexity: O(N * N/2)
• Space Complexity: O(N * N/2)

Đặt vấn đề như bài toán quy hoạch động:

• dp[i][k]: Tổng hạnh phúc lớn nhất có thể sau khi xét ~i~ món quà và đã chọn ~k~ món cho Téo.
• Công thức truy hồi: dp[i][k] = max(dp[i-1][k] + b[i], dp[i-1][k-1] + a[i])
• Điều kiện: ~k \le N/2~.

Với ~N=500,000~, DP không khả thi do yêu cầu bộ nhớ ~O(N^2)~ và thời gian ~O(N^2)~. Đây chỉ là cách tiếp cận minh họa cho bài toán con tập hợp (Subset Selection) khi ~N~ nhỏ.

Cách Thư viện - std::nth_element

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<pair<int, int>> gifts(N);
    long long sumB = 0;
    for (int i = 0; i < N; ++i) {
        cin >> gifts[i].first >> gifts[i].second;
        sumB += gifts[i].second;
    }
    // Chỉ cần tìm phần tử ở vị trí N/2 để phân chia, không cần sắp xếp toàn bộ
    nth_element(gifts.begin(), gifts.begin() + N/2, gifts.end(), 
        [](const pair<int, int>& x, const pair<int, int>& y) {
            return (x.first - x.second) > (y.first - y.second);
        });
    long long ans = sumB;
    for (int i = 0; i < N / 2; ++i) {
        ans += (gifts[i].first - gifts[i].second);
    }
    cout << ans;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Thay vì sắp xếp toàn bộ mảng (~O(N log N)~), ta chỉ cần tìm ~N/2~ phần tử lớn nhất. Hàm nth_element trong C++ có thể thực hiện việc này với độ phức tạp trung bình là ~O(N)~.

• Hàm này sẽ đặt phần tử ở vị trí thứ ~N/2~ vào đúng vị trí, và đảm bảo các phần tử bên trái đều lớn hơn (theo tiêu chí so sánh).
• Ta chỉ cần lặp và cộng các phần tử từ đầu đến ~N/2 - 1~.
• Đây là cách tối ưu về mặt lý thuyết thuật toán (so với sắp xếp), nhưng trong thực tế với ~N=500,000~, hiệu năng giữa sort và nth_element không chênh lệch quá lớn và sort code dễ đọc hơn.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Biến đổi công thức tổng: Tổng hạnh phúc = Tổng b + Tổng (a - b) của quà Téo nhận. Bài toán quy về chọn N/2 phần tử (a-b) lớn nhất.
• Tính chất 'Greedy': Bài toán có tính chất tham lam. Nếu ta đổi chỗ một món có (a-b) nhỏ hơn trong tập S của Téo bằng một món có (a-b) lớn hơn trong tập của Tỳ, tổng hạnh phúc sẽ tăng lên. Do đó, việc chọn các phần tử lớn nhất là tối ưu.

Lỗi thường gặp

• Lỗi tràn số (Integer Overflow): Tổng hạnh phúc có thể lên tới ~N * 100 \approx 5 \times 10^7~, vượt quá giới hạn của kiểu int (khoảng 2 tỷ). Cần sử dụng kiểu long long (C++) hoặc long (Java).
• Sai quy luật sắp xếp: Sắp xếp sai thứ tự tăng/giảm dẫn đến chọn sai tập quà (chọn những món có a-b nhỏ nhất thay vì lớn nhất).
• Xử lý N lẻ: Đề bài đảm bảo N chẵn, nhưng trong các bài tương tự cần chú ý chia đôi N.