(ソートアルゴリズムの応用7.3.8)UVA 299 Train Swapping(バブルソートを用いて逆対数を計算する)
718 ワード
/*
* 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.
", ans);
}
return 0;
}