7955: 【C3】星际编码大赛：逆序争霸 时间限制: 1 Sec 内存限制: 128 MB 提交: 0 解决: 33 [提交][状态][命题人:zhangyinwei] 题目描述 在银河系年度编程巅峰赛的决赛舞台上，来自机械星的AI选手TX-007和植根于生物科技的异星人选手索菲亚迎来了终极对决。本届压轴题竟是古老地球文献中记载的经典算法问题——「逆序对」统计。 赛事光幕显现出题目细节：给定一个可变长度正整数序列，逆序对定义为序列中位置靠前的数字严格大于位置靠后的数字（即存在下标i<j且a_i>a_j）。 "注意序列可能存在重复元素！"主裁判——由全息粒子构成的上届冠军提醒道。这句话让索菲亚的触须微微颤动，她曾在训练中因重复值处理失误而错失练习赛冠军。而TX-007的电子眼已经浮现出归并排序算法的流程图，金属手指在能量键盘上蓄势待发。 输入 第一行，一个数 n，表示序列中有 n 个数。 第二行 n 个数，表示给定的序列。序列中每个数字不超过 10^9。 输出 输出序列中逆序对的数目。 样例输入 6 5 4 2 6 3 1 样例输出 11 提示 对于 25% 的数据

```cpp #include <iostream> using namespace std; long long merge(int arr[], int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2]; for (int i = 0; i < n1; i++) L[i] = arr[l + i]; for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; int i = 0, j = 0, k = l; long long inv_count = 0; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k++] = L[i++]; } else { arr[k++] = R[j++]; inv_count += n1 - i; } } while (i < n1) { arr[k++] = L[i++]; } while (j < n2) { arr[k++] = R[j++]; } return inv_count; } long long mergeSort(int arr[], int l, int r) { long long inv_count = 0; if (l < r) { int m = l + (r - l) / 2; inv_count += mergeSort(arr, l, m); inv_count += mergeSort(arr, m + 1, r); inv_count += merge(arr, l, m, r); } return inv_count; } int main() { int n; cin >> n; int arr[n]; for (int i = 0; i < n; i++) { cin >> arr[i]; } cout << mergeSort(arr, 0, n - 1) << endl; return 0; } // 额外注意逻辑点： // 1. 输入数据的边界处理。 // 2. 合并过程中逆序对数量的准确计算。 // 3. 确保代码在不同规模的输入下都能高效运行。 ``` [2025-04-19 17:33:00 | AI写代码神器 | 509点数解答]