Hiểu bài toán

Cho một mảng gồm N số nguyên. Mỗi thao tác, bạn chọn hai chỉ số i, j khác nhau sao cho tổng a[i] + a[j] >= 0 và xóa hai phần tử này khỏi mảng. Mục tiêu là thực hiện các thao tác này sao cho số lượng phần tử còn lại trong mảng là ít nhất (tương đương với số thao tác nhiều nhất). Hãy in ra số thao tác có thể thực hiện được.

Ví dụ: Mảng [-1, 2, 5, -1, 3].

• Có thể chọn (-1, 3) -> xóa, mảng còn [2, 5, -1].
• Chọn (2, 5) -> xóa, mảng còn [-1].
• Không thể thực hiện thêm do chỉ còn 1 phần tử. Số thao tác là 2.

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

Cách Two Pointers (Sử dụng mảng đã sắp xếp)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int cnt = 0;
    int l = 0, r = n - 1;
    while (l < r) {
        if (a[l] + a[r] >= 0) {
            cnt++;
            l++;
            r--;
        } else {
            // Nếu a[l] + a[r] < 0, thì số âm a[l] quá nhỏ để ghép với a[r] (có thể dương hoặc âm).
            // Do mảng đã sắp xếp tăng dần, a[l] là số nhỏ nhất còn lại.
            // Nếu a[l] không thể ghép với a[r] (số lớn nhất), nó không thể ghép với bất kỳ số nào khác.
            // Ta loại bỏ a[l] và thử lại.
            l++;
        }
    }
    cout << cnt;
    return 0;
}

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

Cách tiếp cận này sử dụng kỹ thuật Two Pointers sau khi sắp xếp mảng tăng dần.

1. Sắp xếp: Mảng được sắp xếp để các số âm nằm bên trái và số dương nằm bên phải.
2. Hai con trỏ: Dùng l trỏ vào phần tử nhỏ nhất (bên trái) và r trỏ vào phần tử lớn nhất (bên phải).
3. Kiểm tra tổng:
   • Nếu a[l] + a[r] >= 0: Ta có thể ghép hai số này lại để xóa. Tăng biến đếm cnt, thu hẹp dải bằng cách l++ và r--.
   • Nếu a[l] + a[r] < 0: Số âm tại a[l] quá nhỏ. Dù ghép với a[r] (lớn nhất) vẫn không đủ, nên nó không thể ghép với bất kỳ số nào khác (vì các số còn lại đều nhỏ hơn hoặc bằng a[r]). Do đó, ta phải loại bỏ a[l] bằng cách l++.
4. Kết thúc: Khi l >= r, không còn cặp nào để xét, trả về cnt.

Phương pháp này đảm bảo tối ưu vì luôn ưu tiên ghép số âm lớn nhất với số dương lớn nhất nếu có thể, hoặc loại bỏ những số âm không thể ghép.

Cách Greedy (Phân loại và Ghép nối)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<long long> need, pos;
    need.reserve(N);
    pos.reserve(N);

    for (int i = 0; i < N; i++) {
        long long x;
        cin >> x;
        if (x < 0) need.push_back(-x);   // cần một số >= -x để ghép
        else pos.push_back(x);           // không âm
    }

    sort(need.begin(), need.end());
    sort(pos.begin(), pos.end());

    long long match = 0;
    int j = 0;
    for (int i = 0; i < (int)need.size(); i++) {
        while (j < (int)pos.size() && pos[j] < need[i]) j++;
        if (j == (int)pos.size()) break;
        // ghép need[i] với pos[j]
        match++;
        j++;
    }

    long long remain = (long long)pos.size() - match;
    long long ops = match + remain / 2;

    cout << ops;
    return 0;
}

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

Phương pháp này chia vấn đề thành hai loại: số âm và số không âm (dương hoặc 0).

1. Phân loại: Tách mảng thành need (chứa giá trị dương của các số âm, tức là giá trị cần thiết để bù trừ) và pos (các số không âm).
2. Ghép nối âm-dương: Sắp xếp cả hai mảng tăng dần. Dùng con trỏ duyệt qua mảng need và pos. Với mỗi số âm (đã chuyển sang dương), ta tìm số dương đầu tiên trong pos đủ lớn để bù trừ (tức là pos[j] >= need[i]). Đây là bước ghép âm-dương.
3. Xử lý số dương còn lại: Sau khi ghép hết các cặp âm-dương có thể, các số dương còn lại trong mảng pos (số lượng là remain = pos.size() - match) có thể tự ghép với nhau (vì tổng hai số dương luôn >= 0). Số cặp ghép được từ chúng là remain / 2.
4. Tổng kết: Tổng số thao tác là số cặp âm-dương (match) cộng với số cặp dương-dương (remain / 2).

Cách này tách biệt logic ghép âm-dương và dương-dương, giúp dễ hình dung nhưng cần thêm bộ nhớ.

Cách Greedy (Tối ưu từ đầu múi)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<long long> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];

    sort(a.begin(), a.end());
    int l = 0, r = N - 1;
    int ops = 0;

    while (l < r) {
        if (a[l] + a[r] >= 0) {
            ops++;
            l++;
            r--;
        } else {
            l++;
        }
    }

    cout << ops << "\n";
    return 0;
}

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

Đây là phiên bản đơn giản化的 của Two Pointers, logic tương tự.

• Sắp xếp mảng.
• Dùng l ở đầu (số nhỏ nhất) và r ở cuối (số lớn nhất).
• Nếu a[l] + a[r] >= 0: Ghép được, tăng ops, thu hẹp.
• Nếu a[l] + a[r] < 0: a[l] không thể ghép với ai (vì a[r] là lớn nhất rồi), loại bỏ a[l] (l++).

Về cơ bản, đây là cách tiếp cận Greedy trực quan nhất. Nó hiệu quả và ngắn gọn.

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

Bài học kinh nghiệm

• Bài toán có tính chất Greedy: luôn ưu tiên ghép số âm 'khó' nhất (số có giá trị âm lớn nhất về độ lớn tuyệt đối) với số dương lớn nhất nếu có thể.
• Sau khi loại bỏ hết các số âm không thể ghép, các số dương còn lại có thể tự do ghép cặp với nhau.
• Việc sắp xếp mảng là bắt buộc để áp dụng Greedy một cách hiệu quả.

Lỗi thường gặp

• Xử lý sai trường hợp các số âm có giá trị tuyệt đối lớn.
• Không tối ưu được thời gian nếu không dùng Greedy (Ví dụ: Brute Force O(N^2) sẽ bị TLE với N=10^5).
• Tính toán sai số lượng thao tác cuối cùng (ví dụ: quên chia 2 cho các cặp dương-dương).