1311:【例2.5】求逆序对 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 39250 通过数: 9202 【题目描述】 给定一个序列a1,a2,…,an,如果存在i<j并且ai>aj,那么我们称之为逆序对,求逆序对的数目。 【输入】 第一行为n,表示序列长度,接下来的n行,第i+1行表示序列中的第ii个数。 【输出】 所有逆序对总数。
时间: 2024-04-08 10:30:57 浏览: 15
你想要求解一个给定序列的逆序对总数。可以使用归并排序的思想来解决这个问题。以下是一个可能的C++实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
long long merge(vector<int>& nums, int start, int mid, int end) {
vector<int> temp(end - start + 1);
int i = start, j = mid + 1;
long long count = 0;
for (int k = 0; k <= end - start; k++) {
if (i > mid) {
temp[k] = nums[j++];
} else if (j > end) {
temp[k] = nums[i++];
} else if (nums[i] <= nums[j]) {
temp[k] = nums[i++];
} else {
temp[k] = nums[j++];
count += mid - i + 1;
}
}
for (int k = 0; k <= end - start; k++) {
nums[start + k] = temp[k];
}
return count;
}
long long mergeSort(vector<int>& nums, int start, int end) {
if (start >= end) {
return 0;
}
int mid = start + (end - start) / 2;
long long count = mergeSort(nums, start, mid) + mergeSort(nums, mid + 1, end) + merge(nums, start, mid, end);
return count;
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
long long count = mergeSort(nums, 0, n - 1);
cout << count << endl;
return 0;
}
```
你可以将输入的序列长度和具体的序列数值依次输入,然后程序将输出逆序对的总数。
希望这个代码能够帮助到你!如果还有其他问题,请随时提问。