核酸检测（C++）！？‘’？】？

描述

幼儿园的老师组织同学们排队做核酸检测,为了防止队伍混乱,老师给每一位同学都分配了一个编号,希望同学们按照编号从小到大的顺序排队.



kid-queue.JPG



但是同学们在排队的时候并没有按照编号来排队.



对于某位同学来说,如果排在前面的其他某一位同学的编号比他的编号大,那么他们的编号就称为一对“逆序对”.



例如

1 4 3 2 5

队伍中“4 3” “4 2” “3 2”都是逆序对


输入
输入数据包括两行

第一行只有一个整数n(范围[1,10000]),表示学生人数

第二行n个整数,表示队伍中同学们的编号,编号范围[1,n],并且没有重复的编号.


输出
请输出队伍中一共有多少逆序对


输入样例 1 

5
1 4 3 2 5
输出样例 1

3
语言：C++

【以下回答由 GPT 生成】

#include <iostream>
#include <vector>

using namespace std;

int mergeSort(vector<int>& nums, int start, int end) {
    if (start >= end) {
        return 0;
    }

    int mid = start + (end - start) / 2;
    int count = mergeSort(nums, start, mid) + mergeSort(nums, mid+1, end);

    vector<int> temp(end - start + 1);
    int i = start, j = mid + 1, k = 0;
    while (i <= mid && j <= end) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
            count += mid - i + 1;
        }
    }

    while (i <= mid) {
        temp[k++] = nums[i++];
    }

    while (j <= end) {
        temp[k++] = nums[j++];
    }

    for (int i = start, k = 0; i <= end; i++, k++) {
        nums[i] = temp[k];
    }

    return count;
}

int main() {
    int n;
    cin >> n;

    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    int count = mergeSort(nums, 0, n - 1);
    cout << count << endl;

    return 0;
}

通过归并排序的方法，可以计算出数组中逆序对的数量。首先将数组分为两个部分，然后递归地计算每个部分中的逆序对数量，再将两个部分合并时，如果前半部分的数字比后半部分的数字大，则构成逆序对，并且计算逆序对的数量。最后将两个部分排序合并，得到整个数组的逆序对数量。时间复杂度为O(nlogn)，空间复杂度为O(n)。

【相关推荐】

• 你可以看下这个问题的回答https://ask.csdn.net/questions/7638432
• 这篇博客你也可以参考下：C++中的引用到底是什么？？？
• 您还可以看一下 黄强老师的C++模板进阶课程中的 什么是模板？小节, 巩固相关知识点
  
• 除此之外, 这篇博客: 你有一份新的C++书单，请注意查收！中的 作者简介 部分也许能够解决你的问题。

这个最简单的就是双层for循环查找，对于一个a[i]，j=i+1开始，只要a[i]比 a[j]大，就是一对逆序数。
运行结果：

代码：

#include <iostream>
using namespace std;

int main()
{
    int n;
    int* a = 0;
    cin >> n;
    a = new int[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i]; //输入n个人的编号
    }

    int cnt = 0; //逆序数对数
    //遍历所有的编号
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++) //查找a[i]后面比a[i]小的数字
        {
            if (a[i] > a[j])
                cnt++;
            else
                break;
        }
    }
    cout << cnt;
    delete[] a;
    return 0;
}

可以将输入的数存入数组，再使用双层for循环来遍历数组，判断数组前面的数比后面的数大的有多少对即可。

代码如下：

#include <iostream>

using namespace std;

int main(void){
    
    int n;
    int arr[10000];   // 存储最多10000个整数数据的数组 
    int num=0;
    
    cin>>n;   //  获取输入的数据的个数n 
    
    // 从输入获取n个整数 
    for(int i=0;i<n;i++){
        cin>>arr[i];
    
    }

    
    // 遍历数组，寻找逆序数有多少对 
    for(int i=0;i<n-1;i++){
        
        for(int j=i+1;j<n;j++){
            // 如果数组前面的数比后面的数大，则逆序数个数+1 
            if(arr[i]>arr[j]){
                num++;
            }
            
        }
    }
    
    //  打印结果 
    cout<<num;
    
    return 0;
    
}