3715. Minimum number of exchanges

Given a 1∼N The random arrangement of , It is required that only two adjacent numbers can be exchanged at a time , So how many times do you need to exchange at least to make the sequence order from small to large ？

Please find out the minimum exchange times of a sequence to be sorted and the corresponding reverse sequence .

Reverse sequence ： Given n Number 1,2,…,n An arrangement of a1a2…an, Make bi Yes number i The number in reverse order in this arrangement , let me put it another way ,bi Equal to before i More than i The number of those numbers . The sequence b1b2…bn It's called permutation a1a2…an The reverse sequence of (inversion sequence).

Input format

The first line is an integer N.

One in the second line 1∼N Permutation .

Output format

The first row outputs the reverse sequence , The numbers are separated by spaces .

The second line outputs the minimum number of exchanges .

Data range

1≤N≤1000

sample input ：

8
4 8 2 7 5 6 1 3

sample output ：

6 2 5 0 2 2 1 0
18

Code ：

//  The number of bubble sort exchanges is equal to the number of reverse pairs 
/*  To keep the sequence in order ,  The elements in the reverse order pair must directly or indirectly change their relative positions ,  In the title, only adjacent elements can be exchanged  , Therefore, each exchange can only eliminate one reverse pair at most   So the minimum number of exchanges is the number of pairs in reverse order ( Sum of reverse sequence ) */
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int w[N], ans[N], temp[N];
int n;

void merge_sort(int l, int r)
{
    
    if (l >= r)
        return;
    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while (i <= mid || j <= r)
    {
    
        if (j > r || i <= mid && w[i] <= w[j])
            temp[k++] = w[i++];
        else
        {
    
            ans[w[j]] += mid - i + 1;
            temp[k++] = w[j++];
        }
    }

    for (int i = l, j = 0; i <= r; i++, j++)
        w[i] = temp[j];
}
int main()
{
    
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i];

    merge_sort(1, n);
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
    
        cout << ans[i] << " ";
        res += ans[i];
    }

    cout << endl
         << res << endl;

    return 0;
}