题目描述

点上方链接看题目描述啦~

算法1

(暴力枚举) $O(n^2)$

暴力只过了八个数据

C++ 代码

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 100010;

int q[N];
LL cnt;

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> q[i];

    for(int i = 0; i < n; i ++)
        for(int j = i + 1; j < n; j ++)
            if(q[i] > q[j]) cnt ++;

    cout << cnt << endl;

    return 0;
}

算法2

(归并) $O(nlogn)$

C++ 代码

#include <iostream>

using namespace std;
typedef long long   LL; //当一共有10的五次方个数的时候 在全逆序的情况下逆序对的个数为(n-1)*n/2 =五*10^9 爆int

const int N = 100010;
int q[N], tmp[N];

LL merge_sort(int l, int r)     //必须注意返回值类型是LL型 这里必须是LL 这个坑要牢记
{
    if(l == r) return 0;        
    int mid = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);   //左右两段的逆序对数量

    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r)
    {
        if(q[i] <= q[j]) tmp[k ++] = q[i ++];
        else                        //当q[i] > q[j]的时候 构成逆序对 
        {                           //因为左边一段是已经排好序的 所以q[i]后面的都是大于q[i]的
            tmp[k ++] = q[j ++];      //所以从q[i]到mid都可以跟q[j]构成逆序对
            res += mid - i + 1;       //所以逆序对的数量为mid-i+1
        }
    }
    while(i <= mid) tmp[k ++] = q[i ++];
    while(j <= r) tmp[k ++] = q[j ++];

    for(int i = 0, j = l; j <= r; i ++, j ++) q[j] = tmp[i];

    return res;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++)  cin >> q[i];

    LL k = merge_sort(0, n - 1);

    cout << k << endl;

    return 0;
}