資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學用 C++ 統計透過的汽車對
給定一個長度為 N 的陣列，其中只包含 0 和 1。值 1 表示一輛向西行駛的汽車，值 0 表示一輛向東行駛的汽車。
如果汽車 A 和汽車 B 滿足 0<=A<B<N，則我們將透過的汽車對計數加 1。其中 A 向東行駛，B 向西行駛。最終我們將統計 (0,1) 對的數量，其中 0 的索引小於 1 的索引。
讓我們透過例子來理解
輸入 − arr[] = {1,0,1,0,1}
輸出 − 透過的汽車對的數量為：3
解釋 − (0,1) 對，其中 0 的索引小於 1 的索引為 − (arr[1],arr[2]), (arr[1],arr[4]), (arr[3],arr[4])
輸入 − arr[] = {1,0,0,0,0}
輸出 − 透過的汽車對的數量為：0
解釋 − 沒有 (0,1) 對滿足 0 的索引小於 1 的索引。
下面程式中使用的演算法如下
我們將使用兩種方法。第一種是使用兩個 for 迴圈的樸素方法。開始遍歷陣列，當遇到 0 時，再次從該點遍歷到陣列末尾，並在遇到 1 時遞增計數。
取一個包含 0 和 1 的陣列 arr[]。
函式 count_cars(int arr[], int size) 以陣列和長度作為輸入，並返回透過的汽車數量。
將初始計數設為 0。
從索引 i=0 遍歷陣列到 i<length-1。
如果 arr[i] 為 0，則再次從索引 j=i+1 遍歷陣列到 j<length。
對於每個 arr[j] 為 1，將計數遞增，因為對 (arr[i],arr[j]) 為 (0,1) 且 i<j。
最後我們將得到總計數。
返回計數作為結果。
高效方法
在這種方法中，我們將從陣列末尾開始遍歷。統計從末尾開始的所有 1。對於每個第一個 0（從末尾開始），對的數量將是 1 的數量，即 temp。
取一個包含 0 和 1 的陣列 arr[]。
函式 count_cars(int arr[], int size) 以陣列和長度作為輸入，並返回透過的汽車數量。
將初始計數設為 0。
使用 while 迴圈從末尾遍歷陣列，直到 size>=1。
如果 arr[size-1] 為 1，則遞增變數 temp，表示到目前為止找到的 1 的數量。
否則它為 0（其索引小於所有 1，即 remp）。對的數量為 temp。設定 count = count+temp。
遞減 size 以獲取下一個元素。
最後我們將得到總計數。
返回計數作為結果。
示例（樸素方法）
#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;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Count of passing car pairs are: 2
示例（高效方法）
#include<bits/stdc++.h>
using namespace std;
int count_cars(int arr[], int size){
int count = 0;
int temp = 0;
while (size >= 1){
if (arr[size-1] == 1){
temp++;
}
else{
count = 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;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Count of passing car pairs are: 2
255 次瀏覽
