Đề bài ====

Cho một mảng gồm các phần tử (a₁, a₂, a₃ ... a_n). Chọn bất kỳ một đoạn con nào của mảng (a_i, a_i+1 ... a_j) và thay thế đoạn đó bằng giá trị MEX(a_i, a_i+1 ... a_j). Hỏi cần ít nhất bao nhiêu bước để toàn bộ mảng trở thành mảng chỉ chứa số 0.

Liên kết đề bài: https://codeforces.com/problemset/problem/2049/A

Phân tích đề bài ====

Điểm then chốt trong bài toán là vị trí của các phần tử 0 trong mảng. Dựa vào vị trí này, ta phân loại thành 4 trường hợp:

• Nếu toàn bộ mảng đều là 0, trả về 0.
• Nếu không có phần tử nào là 0, trả về 1.
• Nếu chỉ có 0 ở hai đầu mảng, trả về 1.
• Nếu có 0 nằm ở giữa mảng, trả về 2.

Dưới đây là đoạn mã ban đầu:

void mex_destruction() {
    vector<int>array;
    get_array(array);
    int number_array = array.size();
    vector<int> loc_0 = get_location(array);
    // Trường hợp toàn 0
    if(loc_0.size() == number_array){
        cout<<0<<'\n';
        return;
    }
    for(int & it : loc_0){
        // Nếu 0 xuất hiện ở vị trí giữa, trả về 2
        if(it!=0 && it!=number_array-1){
            cout<<2<<"\n";
            return;
        }
    }
    cout<<"1"<<'\n';
}

vector<int> get_location(vector<int> array) {
    vector<int>location;
    for(int i=0 ;i<array.size();i++){
        if(array[i] == 0){
            location.push_back(i);
        }
    }
    return location;
}

Tuy nhiên, chương trình lại gặp lỗi với một trường hợp đặc biệt:

1
4
0 0 1 2

Trong trường hợp này, chương trình cho rằng phần tử 0 thứ hai nằm ở vị trí giữa, nhưng thực tế nó vẫn nằm ở vị trí biên. Để xử lý điều này, cần loại bỏ các phần tử 0 ở hai đầu mảng.

std::vector<int> removeEdgeZeros(const std::vector<int> arr) {
    int n = arr.size();
    int start = 0;
    int end = n - 1;
    while (start < n && arr[start] == 0) {
        start++;
    }
    while (end >= 0 && arr[end] == 0) {
        end--;
    }
    if (start > end) {
        return {};
    }
    return vector<int>(arr.begin() + start, arr.begin() + end + 1);
}

Chương trình đã hoàn thiện. Hiệu suất cũng khá tốt, độ phức tạp thời gian là O(n), chủ yếu do việc tìm vị trí các phần tử 0 và loại bỏ các phần tử 0 ở biên.

Mã nguồn hoàn chỉnh ====

//
// Created by FreeMan on 25-1-7.
//

#include<bits/stdc++.h>

void mex_destruction();

void get_array(std::vector<int>& array);

std::vector<int> removeEdgeZeros(const std::vector<int> arr);

std::vector<int> get_location(std::vector<int> array);

using namespace std;

int main(){
    int number;
    cin>>number;
    while (number>0){
        mex_destruction();
        number--;
    }
}

void mex_destruction() {
    vector<int>array;
    get_array(array);
    int number_array = array.size();
    vector<int> loc_0 = get_location(array);
    // Trường hợp toàn 0
    if(loc_0.size() == number_array){
        cout<<0<<'\n';
        return;
    }
    for(int & it : loc_0){
        // Nếu 0 xuất hiện ở vị trí giữa, trả về 2
        if(it!=0 && it!=number_array-1){
            cout<<2<<"\n";
            return;
        }
    }
    cout<<"1"<<'\n';
}

vector<int> get_location(vector<int> array) {
    vector<int>location;
    for(int i=0 ;i<array.size();i++){
        if(array[i] == 0){
            location.push_back(i);
        }
    }
    return location;
}

void get_array(vector<int> & array) {
    int number_array;
    cin>>number_array;
    while(number_array>0){
        int temp_number;
        cin>>temp_number;
        array.push_back(temp_number);
        number_array--;
    }
    array = removeEdgeZeros(array);
}

std::vector<int> removeEdgeZeros(const std::vector<int> arr) {
    int n = arr.size();
    int start = 0;
    int end = n - 1;
    while (start < n && arr[start] == 0) {
        start++;
    }
    while (end >= 0 && arr[end] == 0) {
        end--;
    }
    if (start > end) {
        return {};
    }
    return vector<int>(arr.begin() + start, arr.begin() + end + 1);
}

Kết luận ==

Có thể tiếp cận bài toán theo hướng khác: đếm số đoạn con được bao bởi các phần tử 0. Bạn có thể tham khảo thêm tại: https://blog.csdn.net/qq_68286180/article/details/144634211