299 - Train Swapping

299

Accepted

View Problem

UVA Problem: 299 - Train Swapping
Time Limit: 3.00 Seconds
Program Language: C++
Publisher: http://www.uvaonlinejudge.org

♣ Try it Out ::

---

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define FOR(i,n) for(int i=0; i<n; i++)
using namespace std;

int InsertionSort(int[], int);

int main()
{
    //freopen("299.in", "r", stdin);

    int N, Len; cin>>N;
    FOR(i,N) {
        cin>>Len;
        int Arr[Len];
        FOR(j,Len)
            cin>>Arr[j];
        cout<<"Optimal train swapping takes "<<InsertionSort(Arr,Len)<<" swaps."<<endl;
    }

    return 0;
}

int InsertionSort(int A[], int len) {
    int i, j, key, swaps = 0;
    for(j = 1; j <= len-1; j++) {
        key = A[j];
        i = j - 1;
        while(i >= 0 && A[i] > key) {
            A[i+1] = A[i];
            i--, swaps++;
        }
        A[i+1] = key;
    }
    return swaps;
}

♣ Source Codes ::

---

• 299 - Train Swapping.cpp
• 299 - Train Swapping.java