Hiểu bài toán

Cho một dãy gồm n số nguyên. Bạn có thể thực hiện thao tác xóa một phần tử có giá trị lớn nhất hoặc nhỏ nhất trong dãy hiện tại. Mục tiêu là tìm số lượng ít nhất các phép xóa cần thiết để tổng các phần tử còn lại trong dãy bằng 0. Dãy rỗng cũng có tổng bằng 0. Với n ≤ 10^5 và |a_i| ≤ 10^9, ta cần một giải pháp hiệu quả để tìm ra một tập hợp con con (subset) của dãy ban đầu sao cho tổng của chúng bằng 0, và số lượng phần tử bị xóa (n - Kích thước tập con) là nhỏ nhất.

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

Cách Tham lam (Greedy)

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

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    ll sum = 0;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }

    sort(a.begin(), a.end());

    int l = 0, r = n - 1;
    int ans = 0;

    while (l <= r && sum != 0) {
        if (sum > 0) {
            sum -= a[r];
            r--;
        } else {
            sum -= a[l];
            l++;
        }
        ans++;
    }

    cout << ans << endl;
    return 0;
}

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

Giả sử dãy con giữ lại có tổng bằng 0. Dãy con này được tạo thành từ các phần tử ban đầu. Các phần tử bị xóa là các phần tử nằm ở hai đầu của dãy đã sắp xếp (vì ta chỉ được xóa min hoặc max). Do đó, dãy con giữ lại phải là một đoạn liên tiếp trong dãy đã sắp xếp.

Thuật toán:

1. Tính tổng ban đầu của dãy.
2. Sắp xếp dãy tăng dần.
3. Dùng hai con trỏ l (bên trái) và r (bên phải).
4. Nếu tổng hiện tại > 0, ta cần giảm tổng. Cách nhanh nhất để giảm tổng là xóa phần tử lớn nhất (a[r]) và lùi r vào trong.
5. Nếu tổng hiện tại < 0, ta cần tăng tổng. Cách nhanh nhất để tăng tổng là xóa phần tử nhỏ nhất (a[l]) và đẩy l ra ngoài.
6. Lặp lại cho đến khi tổng bằng 0. Số lần thực hiện thao tác chính là số phần tử cần xóa.

Cách Tối ưu Tham lam (Dùng mảng, kiểm tra biên)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1000005;
ll a[MAXN];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    if (!(cin >> n)) return 0;
    ll tong = 0;
    for(ll i = 1; i <= n; i++) {
        cin >> a[i];
        tong += a[i];
    }
    sort(a + 1, a + n + 1);
    ll l = 1, r = n, kq = 0;
    while(l <= r) {
        if(tong > 0) {
            tong -= a[r];
            r--;
            kq++;
        } else if(tong < 0) {
            tong -= a[l];
            l++;
            kq++;
        } else if(tong == 0) {
            cout << kq;
            return 0;
        }
    }
    cout << n;
}

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

Đây là phiên bản tối ưu hóa của giải thuật tham lam, sử dụng mảng C-style để giảm overhead và kiểm soát chỉ số chặt chẽ. Logic hoàn toàn tương tự:

• Nếu tổng dương: xóa phần tử lớn nhất (a[r]).
• Nếu tổng âm: xóa phần tử nhỏ nhất (a[l]).
• Nếu tổng bằng 0: dừng lại và in kết quả.
• Nếu vòng lặp kết thúc (l > r) mà vẫn chưa đạt tổng 0 (trường hợp không thể), in ra n (xóa hết).

Cách Quy hoạch động (Dynamic Programming)

// Omitted for brevity, logic described in explanation
#include <bits/stdc++.h>
using namespace std;
// DP approach would involve finding the longest subsequence with sum 0.
// However, given constraints and problem structure, Greedy is superior.
// We provide a conceptual DP for educational purposes.
int main() {
    // Not implemented as it is TLE/OOM for n=10^5
    return 0;
}

• Time Complexity: O(n * W) ~ O(n * 10^9)
• Space Complexity: O(n * W)

Bài toán có thể coi là bài toán cái túi (Knapsack) biến thể: tìm tập con các phần tử sao cho tổng bằng 0 và số lượng phần tử lớn nhất.

• State: dp[i][sum] là số lượng phần tử lớn nhất xét đến phần tử thứ i có tổng là sum.
• Do tổng có thể lên tới 10^14, ta không thể dùng mảng 2 chiều thông thường.
• Có thể dùng map hoặc set để lưu các tổng có thể đạt được, nhưng thời gian chạy sẽ rất lớn (O(N^2) hoặc O(N^3)).
• Giải pháp tham lam ở trên là tối ưu nhất do tính chất đơn điệu của thao tác xóa (chỉ xóa min/max).

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

Bài học kinh nghiệm

• Dãy con giữ lại để tổng bằng 0 phải là một đoạn liên tiếp trong dãy đã sắp xếp. Do đó, các phần tử bị xóa là các phần tử nằm ở hai đầu của dãy ban đầu (sau khi sắp xếp).
• Việc xóa phần tử lớn nhất hoặc nhỏ nhất là một thao tác tham lam tốt. Nếu tổng đang dương, xóa phần tử lớn nhất là cách tốt nhất để giảm tổng. Nếu tổng đang âm, xóa phần tử nhỏ nhất là cách tốt nhất để tăng tổng.
• Bài toán có thể được giải quyết bằng kỹ thuật hai con trỏ (Two Pointers) trên dãy đã sắp xếp.

Lỗi thường gặp

• Không sắp xếp dãy ban đầu trước khi thực hiện thuật toán. Thao tác xóa min/max chỉ có ý nghĩa về giá trị, không về vị trí trong dãy ban đầu, nhưng để thuật toán tham lam hoạt động đúng, ta cần xử lý các giá trị theo thứ tự tăng dần/giảm dần.
• Xử lý sai trường hợp tổng ban đầu bằng 0 (cần 0 phép xóa) hoặc trường hợp không thể đạt tổng 0 (mặc dù theo đề bài, dãy rỗng luôn là một đáp án khả thi, nên thuật toán tham lam sẽ xóa hết phần tử nếu cần).
• Lỗi tràn số nguyên (Overflow) khi tính tổng. Cần sử dụng kiểu dữ liệu 64-bit (long long) vì tổng có thể lên tới 10^5 * 10^9 = 10^14.