Hiểu bài toán

Cho một số nguyên dương lớn biểu diễn dưới dạng chuỗi ký tự số. Nhiệm vụ là xóa đúng một chữ số sao cho số còn lại là lớn nhất có thể. Kết quả cũng được xuất ra dưới dạng chuỗi số.

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

Cách Brute Force (Tử tất cả các trường hợp)

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main() {
    ifstream fin("DELETE.INP");
    ofstream fout("DELETE.OUT");

    string M;
    fin >> M;

    string maxNumber = "";

    for (int i = 0; i < M.length(); ++i) {
        string temp = M.substr(0, i) + M.substr(i + 1);
        if (temp > maxNumber) {
            maxNumber = temp;
        }
    }

    fout << maxNumber << endl;

    return 0;
}

• Time Complexity: O(N^2) hoặc O(N^3) tùy vào cách so sánh chuỗi
• Space Complexity: O(N)

Phương pháp này thử xóa từng chữ số một (tại vị trí i), tạo ra chuỗi con mới và so sánh nó với chuỗi lớn nhất tìm được. Chuỗi lớn nhất là chuỗi có giá trị số lớn nhất.

Vấn đề của phương pháp này là việc tạo chuỗi con mới (substr) và so sánh chuỗi có độ phức tạp cao, thường là O(N) hoặc O(N^2) cho mỗi lần lặp. Với N lên tới 10^5, phương pháp này chắc chắn bị TLE (Time Limit Exceeded).

Cách Greedy (Tham lam)

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

int main() {
    freopen("DELETE.INP", "r", stdin);
    freopen("DELETE.OUT", "w", stdout);
    string s;
    cin >> s;
    int n = s.size();
    for(int i = 0; i < n - 1; i++) {
        if(s[i] < s[i + 1]) {
            s.erase(i, 1);
            cout << s;
            return 0;
        }
    }
    s.pop_back();
    cout << s;
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1) (không tính chuỗi đầu vào)

Đây là cách tiếp cận tối ưu nhất.

Để số thu được là lớn nhất, ta cần ưu tiên tăng số ở các chữ số bên trái (chỗ có trọng số cao nhất).

• Ta duyệt từ trái sang phải. Nếu thấy chữ số tại vị trí i nhỏ hơn chữ số tại vị trí i+1 (ví dụ: ...35...), thì việc xóa chữ số i (xóa 3) sẽ tạo ra số ...5... lớn hơn là xóa chữ số i+1 (xóa 5). Do đó, ta nên xóa chữ số đầu tiên mà nó nhỏ hơn chữ số ngay bên phải nó.
• Nếu duyệt hết chuỗi mà không gặp trường hợp nào như trên (chuỗi giảm dần, ví dụ: 54321), điều đó có nghĩa là mọi chữ số đều lớn hơn hoặc bằng chữ số sau nó. Trong trường hợp này, để số thu được là lớn nhất, ta phải xóa chữ số cuối cùng (vì nó là chữ số có giá trị nhỏ nhất và nằm ở vị trí cuối cùng).

Độ phức tạp: O(N) vì chỉ cần duyệt qua chuỗi một lần.

Cách Greedy (Cải tiến)

#include <bits/stdc++.h>
#define taskname "DELETE"
using namespace std;
int main() {
    ios::sync_with_stdio (false);
    cin.tie (nullptr);

    if (fopen (taskname".inp", "r") ) {
        freopen (taskname".inp", "r", stdin);
        freopen (taskname".out", "w", stdout);
    }

    string s, t;
    cin >> s;
    int r = -1;

    for (int i = 0; i < s.size() - 1; i++) {
        if (s[i] < s[i + 1]) {
            r = i;
            break;
        }
    }

    if (r == -1) r = s.size() - 1;

    for (int i = 0; i < s.size(); i++) {
        if (i != r)
            t += s[i];
    }

    for (int i = 0; i < t.size(); i++)
        cout << t[i];
}

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

Cách tiếp cận này thực hiện logic tương tự như "Greedy" ở trên nhưng tách biệt việc tìm vị trí xóa và việc xây dựng chuỗi kết quả.

1. Tìm chỉ số r của chữ số cần xóa:
   • Duyệt để tìm vị trí đầu tiên i sao cho s[i] < s[i+1]. Nếu tìm thấy, gán r = i và dừng lại.
   • Nếu không tìm thấy (toàn bộ chuỗi là không tăng), gán r = s.size() - 1 (vị trí cuối cùng).
2. Xây dựng chuỗi kết quả t bằng cách nối các ký tự của s trừ ký tự tại vị trí r.

Cách này dễ đọc hơn nhưng sử dụng thêm bộ nhớ O(N) để lưu chuỗi kết quả.

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

Bài học kinh nghiệm

• Bài toán thuộc dạng tham lam (Greedy). Khó khăn nằm ở việc xác định quy luật tham lam đúng.
• Quy luật: Tìm từ trái sang phải chữ số đầu tiên mà nó nhỏ hơn chữ số ngay sau nó, thì xóa chữ số đó. Nếu không có (chuỗi giảm dần), xóa chữ số cuối cùng.
• Việc tối ưu hóa không nằm ở thuật toán (vì thuật toán tham lam là O(N)) mà nằm ở cách xử lý chuỗi để tránh tạo bản sao không cần thiết.

Lỗi thường gặp

• Sử dụng Brute Force tạo quá nhiều chuỗi con mới导致 MLE hoặc TLE.
• Xử lý sai trường hợp chuỗi gồm toàn các chữ số giống nhau (vd: 1111). Trong trường hợp này, thuật toán tham lam sẽ không thấy s[i] < s[i+1] và sẽ xóa ký tự cuối cùng (hoặc đầu tiên, tùy cách cài đặt). Kết quả đúng là xóa bất kỳ ký tự nào cũng được, nhưng phải đảm bảo không truy cập ngoài vùng nhớ.
• Quên xử lý trường hợp chuỗi rỗng sau khi xóa (nếu độ dài chuỗi đầu vào là 1).