Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Tìm số phép toán tối thiểu để làm cho mảng trở nên "đẹp" trong C++

Mô tả vấn đề

Cho một mảng nhị phân bin[] gồm n phần tử (chỉ chứa 0 và 1). Nhiệm vụ là tìm số phép toán tối thiểu để biến mảng này thành một "mảng đẹp".

Mảng đẹp là một mảng nhị phân đặc biệt có mẫu xen kẽ giữa 0 và 1.

Một phép toán bao gồm 3 bước:

  1. Bước 1: Cắt mảng thành hai nửa.
  2. Bước 2: Đảo ngược một trong hai nửa.
  3. Bước 3: Ghép hai nửa lại với nhau.

Ví dụ minh họa

Đầu vào:

bin[] = {1, 0, 1, 0, 0, 1}

Đầu ra:

1

Giải thích:

Cắt mảng, lấy phần con bin[4, 5], đảo ngược nó và ghép lại.

Phương pháp giải quyết

Giải pháp dựa trên việc tìm số lượng phép chuyển đổi tối thiểu, bằng với số lượng số 0 liên tiếp. Các trường hợp cơ bản:

  • Nếu kích thước mảng là 1, nó đã là mảng đẹp.
  • Nếu kích thước mảng là số lẻ, nó không bao giờ trở thành mảng đẹp.

Đối với các mảng có độ dài chẵn, ta kiểm tra tổng số 0 hoặc 1 liên tiếp, đó chính là số phép toán cần thực hiện.

Thuật toán

  1. Khởi tạo: zeroCount, oneCount, consZero = 0
  2. Nếu n == 1, trả về 0
  3. Nếu n % 2 != 0, trả về -1
  4. Duyệt i từ 0 đến n-1:
    • Nếu bin[i] == bin[i+1] == 0, tăng consZero++
  5. Nếu bin[n-1] == bin[0] == 0, tăng consZero++
  6. Trả về consZero

Chương trình minh họa

#include <iostream>
using namespace std;

int minOperations(int bin[], int n) {
    if(n == 1)
        return 0;
    if(n % 2 != 0)
        return -1;
    int consZero = 0;
    for (int i = 0; i < n; ++i) {
        if (i + 1 < n) {
            if (bin[i] == 0 && bin[i + 1] == 0)
                consZero++;
        }
    }
    if (bin[0] == bin[n - 1] && bin[0] == 0)
        consZero++;
    return consZero;
}

int main() {
    int bin[] = {1, 0, 1, 0, 0, 1};
    int n = sizeof(bin) / sizeof(bin[0]);
    cout << "Số phép toán tối thiểu để làm mảng đẹp là " << minOperations(bin, n);
    return 0;
}

Kết quả đầu ra

Số phép toán tối thiểu để làm mảng đẹp là 1