Acwing3715. Minimum exchange times (simulation idea of bubble sorting method)

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

To keep the sequence in order , The elements in the reverse order pair must directly or indirectly change their relative positions , And 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 <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e3 + 10;

int n, res;
int a[N], b[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j < i; ++j)
            if (a[j] > a[i])
                b[a[i]]++;
    for (int i = 1; i <= n; ++i)
        printf("%d ", b[i]), res += b[i];
    printf("\n%d\n", res);
    return 0;
}

 

Algorithm ideas
For the first small problem , direct Violent simulation bubble sort .
For the second small problem , Now find the corresponding number in the array , Then just enumerate .

Time complexity
Bubble sort complexity is O(n^2) Of . Find that both numbers and enumerations are linear , Plus sequence enumeration , stay O(n^2) about . Sum up , The time complexity is O(n^2).