当前位置：首页 > news >正文

牛客网刷题：NC208813求逆序数

news 2025/5/17 13:09:11

牛客网刷题：NC208813求逆序数

问题描述

在这里插入图片描述

在排序和数据结构分析中，逆序数是一个重要的概念。对于一个数列来说，如果一对数的前后位置与大小顺序相反（即前面的数大于后面的数），那么它们就称为一个逆序对。一个排列中所有逆序对的总数称为这个排列的逆序数。

例如：对于数列 [2, 4, 3, 1]，存在以下逆序对：

(2, 1)：2 > 1，且 2 在 1 的前面
(4, 3)：4 > 3，且 4 在 3 的前面
(4, 1)：4 > 1，且 4 在 1 的前面
(3, 1)：3 > 1，且 3 在 1 的前面

因此，该数列的逆序数为 4。

问题来源

链接：牛客网 NC208813
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M

输入输出格式

输入格式

第一行为整数 N，表示数列的元素个数 (N ≤ 1000)
第二行为 N 个用空格隔开的整数，值在 int 范围内

输出格式

输出一个整数，表示逆序数的个数

示例

输入：

4
2 4 3 1

输出：

解题思路

本题要求统计数列中的逆序对数量。最直接的方法是使用两层循环遍历所有可能的数对，检查是否构成逆序对。

具体做法：

读取数列长度 n 和所有元素
使用两层循环，外层从 1 到 n，内层从 i+1 到 n
对于每一对元素 (a[i], a[j])，如果 a[i] > a[j]，则逆序数加 1
最后输出总的逆序数

代码实现

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;int a[n];for(int i=1;i<=n;i++)cin>>a[i];int s=0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(a[i]>a[j])s+=1;else continue;}}cout<<s;return 0;
}

代码解析

头文件和命名空间：
```
#include<bits/stdc++.h>
using namespace std;
```
这里引入了标准库的所有内容，简化了编程过程。
读取输入：
```
int n;
cin>>n;
int a[n];
for(int i=1;i<=n;i++)cin>>a[i];
```
注意这里使用了从1开始的下标，这是一种编程习惯，在某些算法问题中比较常见。
计算逆序对：
```
int s=0;
for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(a[i]>a[j])s+=1;else continue;}
}
```
两层循环遍历所有可能的数对，当发现 a[i] > a[j] 且 i < j 时，说明找到一个逆序对，计数器 s 加 1。
输出结果：
```
cout<<s;
return 0;
```
最后输出逆序数的总和。