网站的首页设计,焦作市建设工程网站,网站首页分辨率,在南海建设工程交易中心网站题目 给定一个长度为 n 的整数数列#xff0c;请你计算数列中的逆序对的数量。 逆序对的定义如下#xff1a;对于数列的第 i个和第 j 个元素#xff0c;如果满足 ij且 a[i]a[j]#xff0c;则其为一个逆序对#xff1b;否则不是。 输入格式 第一行包含整数 n#…题目 给定一个长度为 n 的整数数列请你计算数列中的逆序对的数量。 逆序对的定义如下对于数列的第 i个和第 j 个元素如果满足 ij且 a[i]a[j]则其为一个逆序对否则不是。 输入格式 第一行包含整数 n表示数列的长度。 第二行包含 n 个整数表示整个数列。 输出格式 输出一个整数表示逆序对的个数。 数据范围 1≤n≤100000数列中的元素的取值范围 [1,109]。 输入样例 6 2 3 4 5 6 1 输出样例 5 来源AcWing 算法基础 788. 逆序对的数量 思路注意事项 题解
#includeiostreamusing namespace std;typedef long long LL; // 定义 long long 类型为 LL方便使用const int N 100001; // 定义数组的最大长度int n; // 数组的长度
int a[N], tmp[N]; // a[] 是原始数组tmp[] 是归并排序时使用的临时数组// 归并排序函数返回区间 [l, r] 内的逆序对数量
LL merge_sort(int l, int r)
{if (l r) return 0; // 如果区间只有一个元素或没有元素逆序对数量为 0int mid l r 1; // 计算区间的中点LL rep merge_sort(l, mid) merge_sort(mid 1, r); // 递归计算左右两半的逆序对数量int k 0, i l, j mid 1; // k 是 tmp 数组的索引i 和 j 分别是左右两半的起始索引while (i mid j r) // 合并左右两半{if (a[i] a[j]) // 如果左半部分的元素小于等于右半部分的元素tmp[k] a[i]; // 将左半部分的元素放入 tmp 数组else // 如果右半部分的元素小于左半部分的元素{tmp[k] a[j]; // 将右半部分的元素放入 tmp 数组rep mid - i 1; // 增加逆序对的数量因为 a[j] 比 a[i..mid] 都小}}// 将剩余的元素放入 tmp 数组while (i mid) tmp[k] a[i];while (j r) tmp[k] a[j];// 将 tmp 数组中的元素复制回原数组 afor (i l, k 0; i r; i, k) a[i] tmp[k];return rep; // 返回当前区间的逆序对数量
}int main()
{cin n; // 输入数组的长度for (int i 0; i n; i) cin a[i]; // 输入数组的元素LL sum merge_sort(0, n - 1); // 调用归并排序函数计算逆序对的总数cout sum; // 输出逆序对的总数return 0;
}纯代码
#includeiostreamusing namespace std;typedef long long LL; const int N 100001;int n;
int a[N],tmp[N];LL merge_sort (int l, int r)
{if (l r) return 0;int mid l r 1;LL rep merge_sort (l , mid) merge_sort (mid 1, r);int k 0, i l, j mid 1;while (i mid j r)if (a[i] a[j]) tmp[k ] a[i ];else {tmp[k ] a[j ];rep mid - i 1;}while (i mid) tmp[k ] a[i ];while (j r) tmp[k ] a[j ];for (i l, k 0; i r; i , k ) a[i] tmp[k];return rep;
}int main()
{cin n;for (int i 0; i n; i ) cin a[i];LL sum merge_sort (0, n - 1);cout sum;return 0;
}
