4 条评论
-
admin SU @ 2025-7-28 15:14:41
#include <iostream> #include <vector> using namespace std; /** * 合并两个有序子数组，并统计跨越两个子数组的逆序对数量 * @param arr 原始数组 * @param temp 临时数组，用于合并过程 * @param left 左子数组的起始索引 * @param mid 左子数组的结束索引（mid+1 是右子数组的起始） * @param right 右子数组的结束索引 * @return 跨越左右子数组的逆序对数量 */ long long merge(vector<int>& arr, vector<int>& temp, int left, int mid, int right) { int i = left; // 左子数组的当前索引 int j = mid + 1; // 右子数组的当前索引 int k = left; // 临时数组的当前填充位置 long long inv_count = 0; // 逆序对计数器 // 合并两个子数组，同时统计逆序对 while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { // 左子数组元素较小，直接放入临时数组 temp[k++] = arr[i++]; } else { // 右子数组元素较小，形成逆序对 temp[k++] = arr[j++]; // 左子数组中从 i 到 mid 的所有元素都与 arr[j] 形成逆序对 inv_count += (mid - i + 1); } } // 将左子数组剩余元素复制到临时数组 while (i <= mid) { temp[k++] = arr[i++]; } // 将右子数组剩余元素复制到临时数组 while (j <= right) { temp[k++] = arr[j++]; } // 将合并后的结果从临时数组复制回原数组 for (i = left; i <= right; i++) { arr[i] = temp[i]; } return inv_count; } /** * 归并排序主函数，递归分割数组并统计逆序对 * @param arr 原始数组 * @param temp 临时数组，用于合并过程 * @param left 当前处理区间的左边界 * @param right 当前处理区间的右边界 * @return 当前区间内的逆序对总数 */ long long mergeSort(vector<int>& arr, vector<int>& temp, int left, int right) { long long inv_count = 0; if (left < right) { int mid = (left + right) / 2; // 计算中间点，分割数组 // 递归处理左半部分，累加逆序对 inv_count += mergeSort(arr, temp, left, mid); // 递归处理右半部分，累加逆序对 inv_count += mergeSort(arr, temp, mid + 1, right); // 合并两个有序子数组，累加跨越两部分的逆序对 inv_count += merge(arr, temp, left, mid, right); } return inv_count; } /** * 计算数组中的逆序对总数 * @param arr 输入数组 * @return 数组中的逆序对总数 */ long long countInversions(vector<int>& arr) { int n = arr.size(); vector<int> temp(n); // 创建临时数组 return mergeSort(arr, temp, 0, n - 1); // 调用归并排序并返回结果 } int main() { // 优化输入输出性能 ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; // 读取数组长度 vector<int> arr(n); for (int i = 0; i < n; i++) { cin >> arr[i]; // 读取数组元素 } // 计算并输出逆序对数量 cout << countInversions(arr) << endl; return 0; } -
@ 2025-7-28 14:59:50
#include <iostream> #include <vector> using namespace std; // 合并两个有序数组并统计逆序对 long long merge(vector<int>& arr, vector<int>& temp, int left, int mid, int right) { int i = left; // 左子数组的起始索引 int j = mid + 1; // 右子数组的起始索引 int k = left; // 临时数组的起始索引 long long inv_count = 0; // 合并两个子数组并统计逆序对 while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; // 左子数组中剩余的元素都与当前元素形成逆序对 inv_count += (mid - i + 1); } } // 复制左子数组剩余元素 while (i <= mid) { temp[k++] = arr[i++]; } // 复制右子数组剩余元素 while (j <= right) { temp[k++] = arr[j++]; } // 将合并结果复制回原数组 for (i = left; i <= right; i++) { arr[i] = temp[i]; } return inv_count; } // 归并排序并统计逆序对 long long mergeSort(vector<int>& arr, vector<int>& temp, int left, int right) { long long inv_count = 0; if (left < right) { int mid = (left + right) / 2; // 递归处理左子数组 inv_count += mergeSort(arr, temp, left, mid); // 递归处理右子数组 inv_count += mergeSort(arr, temp, mid + 1, right); // 合并并统计逆序对 inv_count += merge(arr, temp, left, mid, right); } return inv_count; } // 计算逆序对总数 long long countInversions(vector<int>& arr) { int n = arr.size(); vector<int> temp(n); return mergeSort(arr, temp, 0, n - 1); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> arr(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } cout << countInversions(arr) << endl; return 0; } -
@ 2025-7-28 14:59:25
#include <iostream> using namespace std; const int MAXN = 5e5 + 5; int arr[MAXN]; int temp[MAXN]; // 临时数组用于合并操作 // 合并两个已排序的子数组并返回逆序对数量 long long merge(int arr[], int left, int mid, int right, int temp[]) { int n1 = mid - left + 1; int n2 = right - mid; // 不需要复制到临时数组L和R，直接使用原数组和temp数组 int i = left; // 左子数组的起始索引 int j = mid + 1; // 右子数组的起始索引 int k = left; // 临时数组的起始索引 long long inv_count = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; // 统计逆序对：左子数组中剩余的所有元素都与当前右子数组元素构成逆序对 inv_count += (mid - i + 1); } } // 复制剩余元素 while (i <= mid) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; // 将临时数组复制回原数组 for (i = left; i <= right; i++) { arr[i] = temp[i]; } return inv_count; } // 归并排序并返回逆序对数量 long long mergeSort(int arr[], int left, int right, int temp[]) { long long inv_count = 0; if (left < right) { int mid = left + (right - left) / 2; // 避免整数溢出 inv_count += mergeSort(arr, left, mid, temp); inv_count += mergeSort(arr, mid + 1, right, temp); inv_count += merge(arr, left, mid, right, temp); } return inv_count; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 0; i < n; i++) { cin >> arr[i]; } long long inversions = mergeSort(arr, 0, n - 1, temp); cout << inversions << endl; return 0; } -
@ 2025-7-28 14:51:03
#include <iostream> using namespace std; const int MAXN = 5e5 + 5; int arr[MAXN]; int temp[MAXN]; // 临时数组用于合并操作 // 合并两个已排序的子数组并返回逆序对数量 long long merge(int arr[], int left, int mid, int right, int temp[]) { int n1 = mid - left + 1; int n2 = right - mid; // 不需要复制到临时数组L和R，直接使用原数组和temp数组 int i = left; // 左子数组的起始索引 int j = mid + 1; // 右子数组的起始索引 int k = left; // 临时数组的起始索引 long long inv_count = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; // 统计逆序对：左子数组中剩余的所有元素都与当前右子数组元素构成逆序对 inv_count += (mid - i + 1); } } // 复制剩余元素 while (i <= mid) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; // 将临时数组复制回原数组 for (i = left; i <= right; i++) { arr[i] = temp[i]; } return inv_count; } // 归并排序并返回逆序对数量 long long mergeSort(int arr[], int left, int right, int temp[]) { long long inv_count = 0; if (left < right) { //int mid = left + (right - left) / 2; // 避免整数溢出 int mid = (right - left) / 2; inv_count += mergeSort(arr, left, mid, temp); inv_count += mergeSort(arr, mid + 1, right, temp); inv_count += merge(arr, left, mid, right, temp); } return inv_count; } int main() { //请使用较快的输入输出 可以使用scanf printf或者使用下面两行代码 ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 0; i < n; i++) { cin >> arr[i]; } long long inversions = mergeSort(arr, 0, n - 1, temp); cout << inversions << endl; return 0; }
- 1