归并排序

使用归并排序的思想来统计逆序对的数量，同时也可以用来解决本题。首先，定义一个辅助数组temp，用于存储归并排序过程中的临时结果。然后，使用递归的方式将数组分成两半，分别对左半部分和右半部分进行归并排序。在归并的过程中，统计逆序对的数量。最后，返回逆序对的总数并输出。

#include <iostream>
using namespace std;

// 合并函数，将两个有序数组合并为一个有序数组，并返回逆序对数量
int merge(int arr[], int temp[], int left, int mid, int right) {
    int i = left;   // 左半部分数组的起始索引
    int j = mid + 1;    // 右半部分数组的起始索引
    int k = left;   // 临时数组的起始索引
    int count = 0;  // 记录逆序对数量

    // 比较左右两部分数组的元素，将较小的元素放入临时数组中
    while (i <= mid && j <= right) {
        if (arr[i] >= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            count += mid - i + 1;   // 统计逆序对数量
        }
    }

    // 将剩余的元素放入临时数组中
    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    // 将临时数组中的元素复制回原始数组
    for (int p = left; p <= right; p++) {
        arr[p] = temp[p];
    }

    return count;
}

// 归并排序函数，将数组进行归并排序，并返回逆序对数量
int mergeSort(int arr[], int temp[], int left, int right) {
    int count = 0;

    if (left < right) {
        int mid = (left + right) / 2;   // 计算中间位置
        count += mergeSort(arr, temp, left, mid);    // 对左半部分数组进行归并排序
        count += mergeSort(arr, temp, mid + 1, right);   // 对右半部分数组进行归并排序
        count += merge(arr, temp, left, mid, right);  // 合并两个有序数组，并统计逆序对数量
    }

    return count;
}

int main() {
    int n;
    cin >> n;   // 输入人数
    int arr[n]; // 存储身高的数组
    int temp[n];    // 临时数组用于归并排序
    for (int i = 0; i < n; i++) {
        cin >> arr[i];   // 输入每个人的身高
    }

    int count = mergeSort(arr, temp, 0, n - 1);  // 调用归并排序函数，获得逆序对数量
    cout << count << endl;   // 输出逆序对数量

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=5e6+5;
int n,a[N],b[N];
long ans;
void merge(int l,int r){
    if(l==r)return;
    int mid=(l+r)/2;
    merge(l,mid);
    merge(mid+1,r);
    int i=l,j=mid+1;
    for(int k=l;k<=r;k++)
        if(j>r||(i<=mid&&a[i]<a[j]))
            b[k]=a[i++],ans+=r-j+1;
        else b[k]=a[j++];
    for(int i=l;i<=r;i++)a[i]=b[i];
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    merge(1,n);
    cout<<ans;
    return 0;}

本题是逆序对的变形，可以转换思维，把前面数比后面小看作逆序对，归并排序进行从大到小排序即可。

while (i <= mid && j <= r)
    {
        if (a[i] >= a[j])
        {
            c[k++] = a[i++];
        }
        else
        {
            c[k++] = a[j++];
            res = res + mid - i + 1;//统计答案
        }
    }

这么简单还不会有人不会 吧？

首先是创建变量

int a[0xeE],TallerThanMe;/*TallerThanMe表示比第a[i]个人高的人数*/
int n;

接下来就是中心代码

for(int i=1;i<=n;i++)
{
    for(int j=i;j<=n;j++)
    {
        if(a[i]<a[j])
        {
            TallerThanMe++;/*每次遇到比自己高的人就+1，可以省去重新统计*/
        }
    }
}

不要告诉我你不会把输入&输出加在中心代码的上下。

还有，案例的输入是3 1 4 1 5是圆周率的一部分OwO