Đếm cặp xe đi ngược chiều trong C++

Cho mảng độ dài N chỉ chứa 0 và 1. 1 = xe đi về tây, 0 = xe đi về đông. Cặp xe đi ngược chiều: cặp (0,1) với chỉ số 0 < chỉ số 1.

Ví dụ

Đầu vào − arr[] = {1,0,1,0,1}

Đầu ra − 3

Giải thích − (arr[1],arr[2]), (arr[1],arr[4]), (arr[3],arr[4]).

Đầu vào − arr[] = {1,0,0,0,0}

Đầu ra − 0

Phương pháp giải

Cách 1 (naive): 2 vòng lặp, khi gặp 0 thì duyệt tiếp đếm số 1.

Cách 2 (hiệu quả O(N)): Duyệt từ cuối. Đếm số 1 đã thấy (temp). Khi gặp 0, cộng temp vào kết quả (vì 0 này sẽ ghép với tất cả 1 phía sau).

• Cách 1: lặp i, nếu arr[i]==0 lặp j=i+1..n-1 đếm 1.
• Cách 2: while(size>=1), nếu arr[size-1]==1 → temp++, else → count+=temp. size--.

Ví dụ code (naive)

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

int count_cars(int arr[], int size) {
    int count = 0;
    for (int i = 0; i < size - 1; i++)
        if (arr[i] == 0)
            for (int j = i + 1; j < size; j++)
                if (arr[j] == 1) count++;
    return count;
}

int main() {
    int arr[] = {1, 1, 0, 0, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of passing car pairs are: " << count_cars(arr, size);
    return 0;
}

Đầu ra

Count of passing car pairs are: 2

Ví dụ code (hiệu quả)

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

int count_cars(int arr[], int size) {
    int count = 0, temp = 0;
    while (size >= 1) {
        if (arr[size - 1] == 1) temp++;
        else count += temp;
        size--;
    }
    return count;
}

int main() {
    int arr[] = {1, 1, 0, 1, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of passing car pairs are: " << count_cars(arr, size);
    return 0;
}

Đầu ra

Count of passing car pairs are: 2