秋招每日一题T25——最少交换次数

题目描述

给定一个 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

思路

〇本题来自北京师范大学考研上机题。
①可以拆解为两道小题，冒泡排序和求逆序数。由于本题的数据规模很小，因此两个问题都可以用暴力枚举解决。
②借此复习一下冒泡排序，两个循环，记住模板即可。
③求逆序数的时候需要特别注意，b[i]等于该排列中先于 i 又大于 i 的那些数的个数，这个i是从1→n的i，因此先从1→n枚举i，找到i在数组中的位置pos，然后再开一重循环，统计从1→pos有多少个数大于i，这个数就是i的逆序数（有点怪绕）。

代码

#include 
#include 
#include 
using namespace std;
const int maxn = 1005;
int n,ans = 0;
int a[maxn] = {0};
int b[maxn] = {0};
int c[maxn] = {0};
int find(int x){
	for(int i=1;i<=n;i++){
		if(b[i] == x){
			return i;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i] = a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n-i;j++){
			if(a[j] > a[j+1]){
				swap(a[j],a[j+1]);
				ans ++;
			}
		}
	}
	for(int i=1;i<=n;i++){
		int pos = find(i);
		for(int j=1;j<pos;j++){
			if(b[j] > i){
				c[i] ++;
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<c[i]<<' ';
	}
	cout<<endl;
	cout<<ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48