題目: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呢@@

測資量應該蠻大的吧?

文章標籤
創作者介紹

Tube's World

Tube 發表在 痞客邦 PIXNET 留言(0) 人氣()