Tuesday, February 5, 2008

Train Swapping : Problem No. 299

Submitted solution with Rum Time = 0.010

#include<iostream>
#include<vector>

using namespace std;

int main()
{
int count=0,n,t,i,j,k,m;
vector<int> car;

cin>>n;

for(i=0;i<n;i++)
{
cin>>t;
if(t==1)
{cin>>j;
cout<<"Optimal train swapping takes 0 swaps."<<endl;
}
else
{
car.resize(t);
for(j=0;j<t;j++)
{
cin>>car[j];
}
for(j=0;j<t;j++)
{
for(k=0;k<t-j-1;k++)
{
if(car[k+1]<car[k])
{
m=car[k+1];
car[k+1]=car[k];
car[k]=m;
count++;
}
}
}
cout<<"Optimal train swapping takes "<<count<<" swaps."<<endl;
count=0;
}
}
return 0;
}

Comment for better algorithm or lesser run time.

No comments: