[Training] GCJ 2021 Qualification Round - Reversort

 第一次參加 GCJ，之前一直沒時間完成這個夢想，這次勇敢踏出第一步。

Qualification Round 已經晉級，我檢討並總結自己的 Code，將比較好的寫法整理下來。

第一題 Reversort 很簡單，沒太大的問題。

題目要求實現 Reversort 演算法，Pseudo Code 已經給予，直接依照 Pseudo Code 刻程式碼即可：

Reversort(L):

  for i := 1 to length(L) - 1

    j := position with the minimum value in L between i and length(L), inclusive

    Reverse(L[i..j])

這裡要注意，矩陣 reverse 有既有的函式可以用，以及 Case 輸出 index 是從 1 開始計，而非 0 開始起算。

以下是我總結較好的寫法：

// by EdocZec on 2021/04/03
// Google Code Jam 2021-01

#include <bits/stdc++.h>
using namespace std;

template<typename T>
ostream& operator<<(ostream&os, const vector<T>& v)
{
    for(int i=0; i<v.size(); i++)
        os << v[i] << " ";
    return os;
}
int readi()
{
    int i;
    cin >> i;
    return i;
}
int alg(vector<int>& a)
{
    int score = 0;
    for(int i=0; i<(a.size()-1); i++)
    {
       int min_idx = i;
       for(int j=i+1; j<(a.size()); j++) 
       {
            if(a[min_idx] > a[j])    min_idx = j;   
       }
       score += min_idx - i + 1;
       reverse(a.begin()+i, a.begin()+min_idx+1);
    }
    return score;
}
int main(int argc, char** argv)
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t, len;

    cin >> t;

    for(int i=0; i<t; i++)
    {
        cin >> len;
        vector<int> a;
        for(int j=0; j<len; j++)    a.push_back(readi());
        //cout << "[Debug] " << a << endl;

        int score = alg(a);
        cout << "Case #" << i+1 << ": " << score << endl; 
    }
    return 0;
}

下一篇將會檢討 Qualification Round 其他的題目。