【60分】枚举数对求解/冒泡排序求解、$O(N^2)$

枚举数对

#include<bits/stdc++.h>
using namespace std;
int n;
int a[1000000+5];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	int cnt=0;//计数器
	for(int i=1;i<=n;i++){
		//a[i] 和后面的数组成了几对逆序对
		for(int j=i+1;j<=n;j++)
		{
			//检查 a[i] 与 a[j] 是否逆序 
			if(a[i]>a[j])
				cnt++;	
		} 
	} 
	cout<<cnt<<"\n";
	return 0;
}

冒泡排序

每次相邻元素交换都恰好消除了一对逆序对。

#include <bits/stdc++.h>
using namespace std;
int n, ans;
int a[1000006];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    ans = 0;
    //最多执行 n-1 轮冒泡
    for (int i = 1; i <= n - 1; i++)
        //执行一轮冒泡操作
        for (int j = 1; j <= n - 1; j++)
            //比较相邻元素
            if (a[j] > a[j + 1])
            {
                swap(a[j], a[j + 1]);
                ans++; //交换次数计数
            }
    cout << ans;
    return 0;
}

【100分】归并排序求逆序对、$O(N\log N)$

#include <bits/stdc++.h>
using namespace std;
long long n;
long long a[1123456];
long long ans;        // <--- 求逆序对相关操作
long long t[1123456]; //临时辅助数组
//将有序的 a[l] ~ a[mid] 及有序的 a[mid+1] ~ a[r] 有序合并
void merge_array(long long l, long long r)
{
    // 1. 有序放入临时数组
    long long mid = (l + r) / 2;
    long long pl, pr, pt;
    pl = l;       // l ~ mid
    pr = mid + 1; // mid+1 ~ r
    pt = l;       // l~r
    //两边都还有元素
    while (pl <= mid && pr <= r)
    {
        if (a[pl] <= a[pr])
        {
            // 可简写为 t[pt++] = a[pl++];
            t[pt] = a[pl];
            pt++;
            pl++;
        }
        else
        {
            ans += mid - pl + 1; // <---
            t[pt] = a[pr];
            pt++;
            pr++;
        }
    }
    //只有一边有元素
    while (pl <= mid)
    {
        t[pt] = a[pl];
        pt++;
        pl++;
    }
    while (pr <= r)
    {
        t[pt] = a[pr];
        pt++;
        pr++;
    }
    // 2. 从临时数组覆盖回来
    for (long long i = l; i <= r; i++)
        a[i] = t[i];
}
//对 a[l] ~ a[r] 排序
void merge_sort(long long l, long long r)
{
    if (l == r)
        return;
    long long mid = (l + r) / 2;
    merge_sort(l, mid);     //对左半边排序
    merge_sort(mid + 1, r); //对右半边排序
    merge_array(l, r);      //将有序的左右合并
}
int main()
{
    cin >> n;
    for (long long i = 1; i <= n; i++)
        cin >> a[i];
    ans = 0; // <---
    merge_sort(1, n);
    cout << ans << "\n"; // <---
    return 0;
}