จำนวนการดำเนินการน้อยที่สุดบนอาร์เรย์เพื่อทำให้สมาชิกทั้งหมดเป็น 0 ด้วย C++

ข้อความโจทย์

กำหนดอาร์เรย์ขนาด N และแต่ละสมาชิกเป็น 1 หรือ 0 งานคือคำนวณจำนวนการดำเนินการขั้นต่ำที่ต้องทำเพื่อแปลงสมาชิกทั้งหมดเป็นศูนย์ สามารถทำการดำเนินการดังต่อไปนี้ -

ถ้าสมาชิกเป็น 1 คุณสามารถเปลี่ยนค่าเป็น 0 ได้ แล้ว -

• ถ้าสมาชิกถัดไปติดกันเป็น 1 จะถูกแปลงเป็น 0 อัตโนมัติ
• ถ้าสมาชิกถัดไปติดกันเป็น 0 แล้ว ไม่มีอะไรเกิดขึ้น

ถ้า arr[] = {1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1} แล้วต้องการ 4 การดำเนินการเพื่อทำให้สมาชิกทั้งหมดเป็นศูนย์

อัลกอริทึม

1. ถ้าสมาชิกปัจจุบันเป็น 1 ให้เพิ่มตัวนับ และค้นหา 0 ถัดไป เพราะ 1 ที่ติดกันทั้งหมดจะถูกแปลงเป็น 0 อัตโนมัติ
2. คืนค่าตัวนับสุดท้าย

ตัวอย่างโค้ด

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

int performMinOperation(int *arr, int n) {
    int i, cnt = 0;
    for (i = 0; i < n; ++i) {
        if (arr[i] == 1) {
            int j;
            for (j = i + 1; j < n; ++j) {
                if (arr[j] == 0) {
                    break;
                }
            }
            i = j - 1;
            ++cnt;
        }
    }
    return cnt;
}

int main() {
    int arr[] = {1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1};
    cout << "Minimum required operations = " << performMinOperation(arr, SIZE(arr)) << endl;
    return 0;
}

ผลลัพธ์

เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้ -

Minimum required operations = 4