算法基础课题解合集

首先您可以尝试用 $O(n^2)$ 的暴力算法来求解，但显然会 $T$ 掉。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int n;
int a[N], res;

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i];
    for (int i = 0; i < n - 1; i ++)
        for (int j = i + 1; j < n; j ++)
            if (a[i] > a[j])
                res ++;
    cout << res << endl;
    return 0;
}

所以，我们就得用归并排序来做这道题。

算法思路

我们都知道，归并排序合并时，是合并两个有序的序列，我们不妨看看下图。

我们可以发现，如果 $4$ 能够和 $1$ 构成逆序对，那么 $5$ 和 $6$，也一定能够构成逆序对（因为数据是从小到大排序的）。

如此，我们就可以快速的统计出逆序对的数量。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

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

//归并排序板子稍加修改
int merge_sort(int l, int r)
{
    if (l == r) return 0;
    int mid = l + r >> 1;
    int res = merge_sort(l, mid) + merge_sort(mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++] = q[i ++];
        else 
        {
            tmp[k ++] = q[j ++];
            //根据上面的图，我们可以发现逆序对的数量就是mid-i+1
            res += mid - i + 1;
        }
    while (i <= mid)
        tmp[k ++] = q[i ++];
    while (j <= r)
        tmp[k ++] = q[j ++];
    for (int i = l, j = 0; i <= r; i ++, j ++)
        q[i] = tmp[j];
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++)
        scanf("%d", &q[i]);
    printf("%d", merge_sort(0, n - 1));
    return 0;
}

但是，这个代码还是 $WA$ 的，因为

不开long long见祖宗

所以我们就把函数的返回值和 $res$ 的值设为 $long\enspace long$ 类型即可。

$AC$ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long LL;
const int N = 100010;
int n, q[N], tmp[N];

LL merge_sort(int l, int r)
{
    if (l == r) return 0;
    int mid = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++] = q[i ++];
        else 
        {
            tmp[k ++] = q[j ++];
            res += mid - i + 1;
        }
    while (i <= mid)
        tmp[k ++] = q[i ++];
    while (j <= r)
        tmp[k ++] = q[j ++];
    for (int i = l, j = 0; i <= r; i ++, j ++)
        q[i] = tmp[j];
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++)
        scanf("%d", &q[i]);
    printf("%lld", merge_sort(0, n - 1));
    return 0;
}

好啦，这篇题解到这里就结束啦！感谢观看！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$