Hiểu bài toán

Bài toán yêu cầu tìm cách xóa ít nhất các phần tử trong một dãy số để dãy còn lại có tổng bằng K. Ta cần tìm một dãy con liên tiếp có tổng bằng K và độ dài lớn nhất có thể. Số lượng thao tác xóa ít nhất sẽ bằng tổng số phần tử ban đầu (n) trừ đi độ dài dãy con tìm được.

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

Cách Two Pointers (Sliding Window)

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

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

    freopen("REMOVE.INP", "r", stdin);
    freopen("REMOVE.OUT", "w", stdout);

    int n;
    long long k;
    cin >> n >> k;

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

    long long sum = 0;
    int l = 0, best = 0;

    for (int r = 0; r < n; r++) {
        sum += a[r];
        while (sum > k) {
            sum -= a[l];
            l++;
        }
        if (sum == k) {
            best = max(best, r - l + 1);
        }
    }

    cout << n - best;
    return 0;
}

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

Sử dụng kỹ thuật Sliding Window (hai con trỏ). Duyệt qua mảng bằng con trỏ 'r' (phải), duy trì tổng hiện tại của cửa sổ. Nếu tổng vượt quá K, ta thu hẹp cửa sổ bằng cách di chuyển con trỏ 'l' (trái) sang phải cho đến khi tổng <= K. Nếu tổng bằng K, ta cập nhật độ dài lớn nhất tìm được. Độ dài dãy con lớn nhất tìm được là 'best'. Số thao tác xóa ít nhất là n - best.

Cách Brute Force (Tối ưu hóa)

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

int main() {
    freopen("REMOVE.INP", "r", stdin);
    freopen("REMOVE.OUT", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    long long sum = 0;
    int left = 0, maxLen = -1;
    for (int right = 0; right < n; right++) {
        sum += a[right];
        while (sum > k && left <= right) {
            sum -= a[left++];
        }
        if (sum == k) {
            maxLen = max(maxLen, right - left + 1);
        }
    }

    cout << n - maxLen;
}

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

Đây là biến thể của thuật toán Sliding Window. Logic tương tự như cách 1. Biến 'maxLen' được khởi tạo là -1 để xử lý trường hợp không tìm thấy dãy con nào (khi đó kết quả là n - (-1) = n+1, nhưng trong ngữ cảnh bài toán, nếu không có dãy con nào, maxLen sẽ không được cập nhật và ta cần xử lý đầu ra đúng. Tuy nhiên, trong các giải pháp này, đều giả định có ít nhất một dãy con hoặc cách xử lý số âm. Giải pháp này nhấn mạnh việc kiểm tra điều kiện 'left <= right' khi thu hẹp cửa sổ.

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

Bài học kinh nghiệm

• Bài toán quy về tìm dãy con liên tiếp có tổng bằng K và độ dài lớn nhất. Số thao tác xóa = n - độ dài dãy con đó.
• Sliding Window là thuật toán tối ưu nhất O(n) cho các bài toán tìm dãy con liên tiếp có tổng thỏa mãn điều kiện (ở đây là bằng K) với dãy số dương.

Lỗi thường gặp

• Quên xử lý các biến kiểu dữ liệu (dùng long long cho tổng và K để tránh tràn số).
• Lỗi logic khi cửa sổ trượt: phải đảm bảo điều kiện dừng của vòng lặp while (sum > k) và cập nhật biên đúng cách.