202503021942 Minimum Inversion Number

Minimum Inversion Number

title: 题目
给定数列 a1, a2, ..., an 的倒数是满足 i < j 和 ai > aj 的对 (ai, aj) 的个数。  
对于给定的数字序列 a1, a2, ..., an，如果我们将前 m 个数字(m>=0)移动到序列的末尾，我们将获得另一个序列。总共有 n 个这样的序列，如下所示：  
a1, a2, ..., an-1, an（其中 m = 0 ）  
a2, a3, ..., an, a1（其中 m = 1）  
a3, a4, ..., an, a1, a2（其中 m = 2）  
...  
an, a1, a2, ..., an-1（其中 m = n-1）  
你被要求编写一个程序，从上述序列中找出最小的倒数。
 
输入由多组测试用例组成。每个案例由两行组成：第一行包含一个正整数 n (n <= 5000)；下一行包含从 0 到 n-1 的 n 个整数的排列。
 
对于每种情况，在一行上输出最小倒数。

title: input
10
1 3 6 9 0 8 5 7 4 2

title: output
16

title: 思路
 
 
 

title:代码
~~~ c ++
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
 
using namespace std;
const int N = 5e3 + 10;
int a[N], b[N], temp[N];
int 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 i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
        {
            res += mid - i + 1;
            temp[k++] = a[j++];
        }
    while (i <= mid)
        temp[k++] = a[i++];
    while (j <= r)
        temp[k++] = a[j++];
 
    for (i = l, j = 0; i <= r; i++, j++)
        a[i] = temp[j];
    return res;
}
 
int main()
{
    while (cin >> n)
    {
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            b[i] = a[i];
        }
        /*
        for (int k = 0; k < n; k++)
            cout << b[k] << " ";
        cout << endl;*/
        int res = merge_sort(0, n - 1);
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1, k = 0; j != i; j++, j %= n, k++)
                a[k] = b[j];
            a[n - 1] = b[i];
            /*
            for (int k = 0; k < n; k++)
                cout << a[k] << " ";
            cout << endl;*/
            res = min(res, merge_sort(0, n - 1));
        }
        cout << res << endl;
    }
 
    return 0;
}
~~~