AcWing 788. 逆序对的数量
\(AcWing\) \(788\). 逆序对的数量
一、题目描述
给定一个长度为 \(n\) 的整数数列,请你计算数列中的逆序对的数量。
逆序对的定义如下:对于数列的第 \(i\) 个和第 \(j\) 个元素,如果满足 \(i<j\)
且 \(a[i]>a[j]\),则其为一个逆序对;否则不是。
输入格式
第一行包含整数 \(n\),表示数列的长度。
第二行包含 \(n\) 个整数,表示整个数列。
输出格式
输出一个整数,表示逆序对的个数。
数据范围
\(1≤n≤100000\),数列中的元素的取值范围 \([1,10^9]\)
输入样例:
6
2 3 4 5 6 1
输出样例:
5
二、什么是逆序对?
大的在前,小的在后,这样有一个算一个。
![](https://img2020.cnblogs.com/blog/8562/202109/8562-20210906094343981-907775927.png)
逆序对包括:\(\{5,2\},\{5,2\},\{5,1\},\{5,4\},\{2,1\},\{2,1\}\),共\(6\)个。
三、暴力大法
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
const int N = 100010;
int a[N];
LL ans;
//暴力大法
/*测试数据
5
5 2 2 1 4
*/
int main() {
cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i];
//暴力大法
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (a[i] > a[j]) ans++;
cout << ans << endl;
return 0;
}
四、答案的数据类型
最终的\(ans\)定义为什么类型?就是说给定范围内的数据,产生的逆序对最多是多少个呢?本题中\(n<=100000\),就是小于\(10^5\)。那么什么情况下逆序对最多呢?就是完全倒序的情况下逆序对最多,那么在有\(n\)个数据的情况下,有多少个逆序对呢?
对于第\(1\)个而言,有\(n-1\)个逆序对,第\(2\)个有\(n-2\)个逆序对,....,第\(n\)个有\(0\)个逆序对。
\(ans=(n-1)+(n-2)+(n-3)+...+1=\frac{n*(n-1)}{2}\)
本题\(n\)最大是\(10^5\),所以\(ans\)最大值是\(ans=100000*(100000-1)/2 \approx 1e{10} \div 2=5*10^9\)
而\(int\)的极限是\(2147483647\),比\(2e9\)大一点点,就是说\(int\)装不下,需要用\(long \ long\):
毫无悬念,\(tle\)妥妥的。
五、多种解法对比
归并排序 | 树状数组 | 线段树+静态数组 | 线段树+离散化+\(STL\) | 线段树+离散化+手写二分 | |
---|---|---|---|---|---|
执行时长 | \(75 ms\) | 待测 | \(344 ms\) | \(342 ms\) | \(284ms\) |
\(AcWing\) | \(√\) | \(√\) | \(√\) | \(√\) | \(√\) |
洛谷 | \(√\) | \(√\) | \(√\) | \(√\) | \(√\) |
总结:STL的二分常数较大,尽量手写二分答题,减少TLE机会。
六、利用归并求逆序对
\(Q\):为什么归并排序可以求逆序对呢?
答:在归并两个子数组时,有三种情况:
(1)、逆序对在左边(红色)
这在调用左侧子数组进行递归时,已经完成了统计,自己不管。(内部问题内部解决)
(2)、逆序对在右边(绿色)
这在调用右侧子数组进行递归时,已经完成了统计,自己不管。(内部问题内部解决)
(3)、逆序对在左侧和右侧(黄色)
这个需要自己来处理,对于右侧的黄色圆,那么在左侧的黄色圆及左侧黄色圆后面,一直到中线的所有数,都是比右侧黄色圆大的,就是有\(mid-i+1\)个逆序对。
可以结合代码来理解原理,其实就是在归并的时刻,只处理合并数组中大小反着的两个数字,一旦发现前面的数字比后面的数字大,就是发现了一个逆序对,同时,由于归并排序的特点,两个要归并的数组是内部有序的,所以,意味着左侧当前数字及左侧当前数字一直到左侧集合结束的所有数字,都比右侧当前数字大!个数就是\(mid-i+1\)个,其中\(l<=i<=mid\)。
七、归并代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int n; // n个数据
int q[N]; // 原数组
int t[N]; // 临时数组
LL res; // 结果
void merge_sort(int q[], int l, int r) {
if (l >= r) return;
int mid = (l + r) >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
if (q[i] <= q[j])
t[k++] = q[i++];
else {
t[k++] = q[j++];
res += mid - i + 1;
}
while (i <= mid) t[k++] = q[i++];
while (j <= r) t[k++] = q[j++];
for (i = l, j = 0; i <= r; i++, j++) q[i] = t[j];
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> q[i];
merge_sort(q, 1, n);
printf("%d\n", res);
return 0;
}
八、树状数组解法
九、线段树+静态数组
相关文章
- LLM-2022:PaLM【参数量:5400亿(540B)】【用于训练的token数量:780B】【基于Pathways的大语言模型】
- 语音信号处理-参数详解(一):n_fft(FFT窗口大小:FFT在时间轴上的长度,以采样点数量表示)【FFT的长度N决定频域中的分辨率】【频域分辨率=采样率/n_fft】【n_fft的选择:】
- NLP-预训练模型-201806-NLG:GPT-1【参数量:117M;训练数据量:1GB】【预训练:GPT使用单向语言模型;Fine-tuning:GPT、Task的参数一起训练】
- 分类模型-评估指标(2):ROC曲线、 AUC值(ROC曲线下的面积)【只能用于二分类模型的评价】【不受类别数量不平衡的影响;不受阈值取值的影响】【AUC的计算方式:统计所有正负样本对中的正序对】
- Linux查看当前目录下文件数量
- Vue 简单实例 购物车2 - 修改商品数量和价格
- 深度学习卷积网络浮点计算量和参数量的计算(附Pytorch代码)
- leetcode200. 岛屿数量
- 德国企业遭网络攻击数量显著增加
- AcWing 788 逆序对的数量 之 树状数组 解法
- 【Darwin学习笔记】之获取系统处理器数量的方法
- 【ybt金牌导航8-6-4】原根数量
- [LeetCode] 750. Number Of Corner Rectangles 边角矩形的数量
- 2018-10-31-C#-程序内的类数量对程序启动的影响
- C# 程序内的类数量对程序启动的影响