有一个隧道,某一天一共有 n 辆车通过且都只通过一次。交通规章规定这个隧道里不能超车,因此在隧道的入口和出口都有监控,能记录下这些车出入隧道的顺序。 但总有一些法外之徒,喜欢飞车,这是很不好的行为。 规定如下: 如果车b 本来是排在车a的后面进入隧道 但隧道中进行了超车行为,于是车b先于车a出隧道了。 现在请求出一共多少辆车发生了超车行为,注意超过一辆车与超过多辆车,都只按一次计算。 即只需要有多少车发生了超车行为c++代码和思路
时间: 2024-03-17 08:47:56 浏览: 74
这道题可以使用归并排序的思想来解决,具体思路如下:
1. 将车辆通过隧道的顺序记录下来,记为数组 a。
2. 定义一个计数器 count,初始值为 0。
3. 实现归并排序算法,每次在合并两个有序数组的时候,统计其中一个数组中的元素在另一个数组中的逆序对个数,然后将两个数组合并并排序。
4. 最终得到排好序的数组 a,并且 count 记录了其中逆序对的个数。
5. count 即为超车行为的次数。
下面是 C++ 的代码实现:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int merge(vector<int>& nums, int left, int mid, int right) {
vector<int> tmp(right - left + 1);
int i = left, j = mid + 1, k = 0, cnt = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
tmp[k++] = nums[i++];
} else {
tmp[k++] = nums[j++];
cnt += mid - i + 1;
}
}
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= right) {
tmp[k++] = nums[j++];
}
for (i = left, k = 0; i <= right; i++, k++) {
nums[i] = tmp[k];
}
return cnt;
}
int mergeSort(vector<int>& nums, int left, int right) {
if (left >= right) {
return 0;
}
int mid = left + (right - left) / 2;
int cnt = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right) + merge(nums, left, mid, right);
return cnt;
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
int cnt = mergeSort(nums, 0, n - 1);
cout << cnt << endl;
return 0;
}
```
时间复杂度为 $O(n\log n)$,空间复杂度为 $O(n)$。