[解题报告] Train Swapping

超、凢脫俗 2022-01-07 12:49 161阅读 0赞

## 题目大意 ##

题目原文：[http://uva.onlinejudge.org/external/2/299.pdf][http_uva.onlinejudge.org_external_2_299.pdf]

## 背景 ##

这道题目是一个很基本的排序问题，而且是冒泡排序问题，题目原题的意思就是叫你将车厢号码重新排序，计算出需要交换的最小次数。

# #

## Example Input ##

3
    3
    1 3 2
    4
    4 3 2 1
    2
    2 1

## Example Output ##

Optimal train swapping takes 1 swaps.
    Optimal train swapping takes 6 swaps.
    Optimal train swapping takes 1 swaps.

# #

算法：

使用冒泡排序就最少交换次数的方法，所以毋庸置疑的选择冒泡排序。这里自己复习下三种排序方法，给个链接[http://wenku.baidu.com/view/c4ace8d87f1922791688e8bc.html][http_wenku.baidu.com_view_c4ace8d87f1922791688e8bc.html]

代码：这里附上我的代码，你可以去[这里][Link 1]提交你的代码验证你的代码是否正确,

1 #include<stdio.h>
     2 int main(void)
     3 {
     4     int n,l,i,j,count,swap,temp=0;
     5     int num[50];
     6 
     7     scanf("%d",&n);
     8     while(n--)
     9     {
    10         count=0;
    11         scanf("%d",&l);
    12 
    13         for(i=0;i<l;i++)
    14         scanf("%d",&num[i]);
    15 
    16         for(i=0;i<l-1;i++)
    17         {
    18             swap=0;      //检验后面的数字顺序是否需要排序不要则退出排序
    19             for(j=0;j<l-i-1;j++)
    20             if(num[j]>num[j+1])
    21                 {
    22                     swap=1;
    23                     temp=num[j+1];
    24                     num[j+1]=num[j];
    25                     num[j]=temp;
    26                     count++;
    27                 }
    28                 if(!swap)break;
    29         }
    30         printf("Optimal train swapping takes %d swaps.\n",count);
    31     }
    32 
    33     return 0;
    34 }

转载于:https://www.cnblogs.com/qisong178878915/archive/2013/02/18/2916369.html

[http_uva.onlinejudge.org_external_2_299.pdf]: http://uva.onlinejudge.org/external/2/299.pdf
[http_wenku.baidu.com_view_c4ace8d87f1922791688e8bc.html]: http://wenku.baidu.com/view/c4ace8d87f1922791688e8bc.html
[Link 1]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=submit_problem&problemid=235&category=