2015
04-16

Manhattan Sort

Yet another sorting problem! In this one, you’re given a sequence S of N distinct integers and are asked to sort it with minimum cost using only one operation:
The Manhattan swap!
Let Si and Sj be two elements of the sequence at positions i and j respectively, applying the Manhattan swap operation to Si and Sj swaps both elements with a cost of |i-j|. For example, given the sequence {9,5,3}, we can sort the sequence with a single Manhattan swap operation by swapping the first and last elements for a total cost of 2 (absolute difference between positions of 9 and 3).

The first line of input contains an integer T, the number of test cases. Each test case consists of 2 lines. The first line consists of a single integer (1 <= N <= 30), the length of the sequence S. The second line contains N space separated integers representing the elements of S. All sequence elements are distinct and fit in 32 bit signed integer.

The first line of input contains an integer T, the number of test cases. Each test case consists of 2 lines. The first line consists of a single integer (1 <= N <= 30), the length of the sequence S. The second line contains N space separated integers representing the elements of S. All sequence elements are distinct and fit in 32 bit signed integer.

2
3
9 5 3
6
6 5 4 3 2 1

Case #1: 2
Case #2: 9

struct node{
int id;
int v;
}p[33];
bool cmp(node a,node b){
return a.v<b.v;
}
int main(){
int t;
scanf("%d",&t);
int ca=1;
while(t--){
int n;
scanf("%d",&n);
int i;
int ans = 0;
for(i=1;i<=n;i++){
scanf("%d",&p[i].v);
p[i].id = i;
}
sort(p+1,p+1+n,cmp);
for(i=1;i<=n;i++){
ans += abs(p[i].id-i);
}
printf("Case #%d: %d\n",ca++,ans/2);
}
return 0;
}