acwing每日一题-6

发表于 更新于 分类于 阅读次数： 本文字数： 704 阅读时长 ≈ 1 分钟
acwing每日一题-最少交换次数

题目

给定一个 1∼N 的随机排列，要求一次只能交换相邻两个数，那么最少需要交换多少次才可以使数列按照从小到大排列呢？

请你求出一个待排序序列的最少交换次数和对应的逆序数列。

逆序数列：给定 n 个数 1,2,…,n 的一个排列 a1a2…an，令 bi 是数 i 在此排列中的逆序数，换句话说，bi 等于该排列中先于 i 又大于 i 的那些数的个数。数列 b1b2…bn 称为排列 a1a2…an 的逆序数列(inversion sequence)。

输入格式

第一行一个整数 N。

第二行一个 1∼N 的排列。

输出格式

第一行输出逆序数列，数之间用空格隔开。

第二行输出最少交换次数。

数据范围

1≤N≤1000

输入样例：

1
2
8
4 8 2 7 5 6 1 3

输出样例：

1
2
6 2 5 0 2 2 1 0
18

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
long long n,num[1010],ans[1010],sum=0;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>num[i];
    for(int i=0;i<n;i++)
    for(int j=0;j<i;j++){
        if(num[j]>num[i])
        ans[num[i]]++;
    }
    for (int i = 1; i <= n; i ++ )
    {
        cout<<ans[i]<<' ';
        sum+=ans[i];
    }
    cout<<endl<<sum;
    return 0;
}