UVa 299 - Train Swapping

浏览数：30 / 时间：2015年06月11日

题目：给你一个序列，每次只能交换相邻的两个数，问使得序列递增的最小的交换次数。

分析：数学，逆序数。

如果在一个序列中存在a[i] > a[j]并且 i < j，则a[i]与a[j]构成一对逆序对；

一个序列的逆序对的总数，就是这个序列的逆序数；

如题，相邻元素交换，每次交换序列逆序数必然改变1，而一个递增的序列逆序数为0；

因此，最少的交换次数即为逆序数，而每次按照逆序对减少的方式交换就得到递增序列。

说明：整理很久以前刷过的题目。

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>

using namespace std;

int data[100];

int main()
{
	int n,m,count;
	while (cin >> n)
	while (n --) {
		cin >> m;
		for (int i = 0 ; i < m ; ++ i)
			cin >> data[i];
		count = 0;
		for (int i = 0 ; i < m ; ++ i)
		for (int j = 0 ; j < i ; ++ j)
			count += (data[j]>data[i]);
		
		cout << "Optimal train swapping takes " << count << " swaps." << endl;
	}
	return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

UVa 299 - Train Swapping