UVA 299: Train Swapping

Jasonlin posted @ 2011年3月28日 12:03 in UVA , 1628 阅读

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=4&problem=235&mosmsg=Submission+received+with+ID+8686327

题目大意:

     按序号从大到小排列火车,相邻之间才能交换。求交换次数。

解题思路:

      就是冒泡法排序嘛~

解题代码:

#include<iostream>
using namespace std;
int t[100];
int n;
int swap(){
	int count=0;
	for(int i=0;i<n-1;i++)
		for(int j=0;j<n-1-i;j++)
			if(t[j]>t[j+1]){
				int tmp=t[j];
				t[j]=t[j+1];
				t[j+1]=tmp;
				count++;
			}
	return count;
}
int main(){
	int cas;
	cin>>cas;
	while(cas--){
		cin>>n;
		for(int i=0;i<n;i++)
			cin>>t[i];
		cout<<"Optimal train swapping takes "<<swap()<<" swaps."<<endl;
	}
	return 0;
}

扩展知识:http://en.wikipedia.org/wiki/Sorting_algorithm

  • 无匹配
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter