【題解】UVA 10152 ShellSort

【題目敘述】https://vjudge.net/problem/UVA-10152
【解題想法】Greedy

  • source[ ]: original ordering of the turtle stack
  • target[ ]: the desired ordering of the stack
  • Ps: 從後面開始比對,紀錄目前在source中的位置
  • Pt: 從後面開始比對,紀錄目前在target中的位置
#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T, n;
    string buf;
    cin >> T;
    while (T--){
        cin >> n;
        getline(cin, buf);
        string target[n], source[n];
        for (int i = 0; i < n; i++){
            getline(cin, source[i]);
        }
        for (int i = 0; i < n; i++){
            getline(cin, target[i]);
        }
        int Pt = n-1, Ps = n-1;
        while (Ps >= 0){
            if (source[Ps] == target[Pt]) Pt--;
            Ps--;
        }
        while (Pt >= 0){
            cout << target[Pt--] << "\n";
        }
        cout << "\n";
    }
    return 0;
}

分享本文 Share with friends