本文主要是介绍3715. 最少交换次数 北京师范大学考研机试题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定一个 1∼N的随机排列，要求一次只能交换相邻两个数，那么最少需要交换多少次才可以使数列按照从小到大排列呢？
请你求出一个待排序序列的最少交换次数和对应的逆序数列。
逆序数列：给定 n 个数 1,2,…,n 的一个排列 a1a2…a，令 bi 是数 i 在此排列中的逆序数，换句话说，bi 等于该排列中先于 i又大于 i的那些数的个数。数列 b1b2…bn 称为排列 a1a2…an 的逆序数列(inversion sequence)。
输入格式
第一行一个整数 N。
第二行一个 1∼N 的排列。
输出格式
第一行输出逆序数列，数之间用空格隔开。
第二行输出最少交换次数。
数据范围
1≤N≤1000
输入样例：
8
4 8 2 7 5 6 1 3
输出样例：
6 2 5 0 2 2 1 0
18
#include<bits/stdc++.h>
using namespace std;
int n;
const int M = 10e4;
int w[M],ans[M];
int m;
int main()
{cin >> n;for(int i = 1; i <= n; i++){cin >>w[i];}for(int i = 1; i <=n; i++){for(int j = 1; j <i ;j++){if(w[j]>w[i])ans[w[i]]++;}}for(int i =1; i <= n; i++){m +=ans[i];cout<<ans[i]<<" ";}cout<<"\n"<<m;return 0;
}这篇关于3715. 最少交换次数 北京师范大学考研机试题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
