数据结构
网络
关系数据库管理系统 (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 次浏览
