Tube's World

題目:http://poj.org/problem?id=1804

其實只要注意觀察題目

就可以發現他的第二種排序法

其實就是倒過來的泡泡排序法

所以只要寫個倒過來的bubble sort即可解決

1. /*****************************************
2. Problem: 1804           User: bruce30262
3. Memory: 388K            Time: 110MS
4. Language: GCC           Result: Accepted
5. ******************************************/
6.  
7. #include <stdio.h>
8.  
9. int main()
10. {
11.     int cases, size, i, j, swap, caseCount = 1;
12.  
13.     scanf("%d",&cases);
14.  
15.     while(cases--)
16.     {
17.         scanf("%d",&size);
18.         int num[size];
19.  
20.         for(i = 0 ; i < size ; i++)
21.         {
22.             scanf("%d",&num[i]);
23.         }
24.  
25.         swap = 0;
26.  
27.         for(i = 0 ; i < size ; i++)
28.         for(j = size - 1 ; j > i ; j--)
29.         {
30.             if(num[j-1] > num[j])
31.             {
32.                 int temp = num[j-1];
33.                 num[j-1] = num[j];
34.                 num[j] = temp;
35.                 swap++;
36.             }
37.         }
38.  
39.         printf("Scenario #%d:\n%d\n\n",caseCount++ ,swap);
40.  
41.     }
42.  
43.     return 0;
44. }

不過執行時間110ms呢@@

測資量應該蠻大的吧?