(排序算法的应用7.3.8)UVA 299 Train Swapping(使用冒泡排序来计算逆序对数)
/* * UVA_299.cpp * * Created on: 2013年11月3日 * Author: Administrator */#include <iostream>#include <cstdio>using namespace std;const int maxn = 55;int main() {int a[maxn];int t;scanf("%d", &t);while (t--) {int n;scanf("%d", &n);int i;for (i = 0; i < n; ++i) {scanf("%d", &a[i]);}int j;int ans = 0;for(i = 0 ; i < n ; ++i){//冒泡排序for(j = i+1; j < n ; ++j){if(a[i] > a[j]){int temp = a[i];a[i] = a[j];a[j] = temp;ans++;//逆序对数+1}}}printf("Optimal train swapping takes %d swaps.\n", ans);}return 0;}