首页 > 代码库 > UVa 299 - Train Swapping

UVa 299 - Train Swapping

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

分析:数学,逆序数。

            如果在一个序列中存在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