內容

Rex參加完了成年禮，只有一句心得：「幹怎麼又薰風格好險不是北極星！」

語畢，他突然想起了那天，被北極星支配的恐懼

那天3號的Rex，不小心聽錯口令，排到了倒數第三個人的位子

於是蝙蝠貓值星官很兇的吼Rex:「你那第幾中隊的R 會不會排隊R 亂七八糟 一點紀律都沒有」

Rex嚇到都快哭了

隊輔馬上帶他回原位，不料蝙蝠貓為了懲罰Rex，把整個n人的班級拆成一排1x(n−1)的混亂隊伍(不含Rex)

並要他使用bubble sort的原則，把隊伍排整齊，最後跟他報告要交換幾次，才讓他排回去。

不過在場人數可能將盡300人，Rex可能排到瘋掉，聰明的你請幫助可憐的Rex脫離北極圈。


輸入說明

輸入有一個n，表示接下來有n個人的直線隊伍

計算排列a₁ an需要幾次

不過需要注意的是：當當前的ai==3 時，則ai不列入排序裡

輸出說明

輸出少了Rex後的隊伍需交換幾次


範例輸入

3

5 3 1

5

1 2 5 3 4

範例輸出

1

1


程式

#include <iostream>
using namespace std;
int main() {
  int n;
  while(cin>>n){
    int arr[n], x = 0;
    for(int i = 0; i < n; i++){
      cin>>arr[i];
    }
    for(int i=0; i < n; i++){
      if(arr[i]==3){                    //判斷陣列裡有沒有3
          for(int j=i; j<(n-1); j++)
              arr[j] = arr[j+1];
          i--;
          n--;
      }
    }
    //bubble sort
    for(int j = 0; j < n; j++){
      for(int h = 0; h < n-1; h++){
        if(arr[h] > arr[h+1]){
          swap(arr[h], arr[h+1]);
          x++;
        }
      }
    }
    cout<<x<<endl;
  }
}

說明

這題跟[C++]Sort yourself 1很像，一開始都一樣，說法不同而已。

輸入完這直線隊伍後，就要把Rex從隊伍裡用掉(我們要排擠他，誰叫上次他用牙齒來搞死我)，用迴圈檢查陣列裡有沒有3，檢查到了，就把他後面的數字全往前走一格。

排完後，就用上次的bubble sort，還要設一個x，隊伍交換的時候就會+1，最後輸出x就是答案了。