ZeroJudge 解題筆記：g797. 洗牌 (Cards)

作者：王一哲
日期：2025年3月28日



ZeroJudge 題目連結：g797. 洗牌 (Cards)

解題想法

這題考陣列操作，可以將陣列先拆開成上、下兩半再合併，或是用另一個陣列儲存洗牌後的資料。

Python 程式碼

寫法1，用串列切片先找出上、下兩半的內容，再合併資料。使用時間約為 26 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # n 張牌，洗牌 m 次
    deck = list(map(int, input().split()))  # 讀取牌面數值
    upp, bot = deck[:n//2], deck[n//2:]  # 分成上、下兩半
    for _ in range(m):  # 執行 m 次
        for i in range(n//2):  # 執行 n//2 次
            deck[2*i] = upp[i]  # 從 upp 及 bot 依序取值放入 deck
            deck[2*i+1] = bot[i]
        upp, bot = deck[:n//2], deck[n//2:]  # 更新 upp、bot
    print(*deck)  # 印出答案

寫法2，滾動串列，將洗牌後的資料先存入另一個串列。使用時間約為 28 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # n 張牌，洗牌 m 次
    deck = list(map(int, input().split()))  # 讀取牌面數值
    for _ in range(m):  # 執行 m 次
        tmp = [0]*n  # 暫存洗牌後的資料
        for i in range(n//2):  # 執行 n//2 次
            tmp[2*i] = deck[i]  # 從 deck 前半取值放入 tmp
            tmp[2*i+1] = deck[n//2 + i]  # 從 deck 後半取值放入 tmp
        deck, tmp = tmp, deck  # 交換 deck、tmp
    print(*deck)  # 印出答案

C++ 程式碼

寫法1，用串列切片先找出上、下兩半的內容，再合併資料。使用時間約為 2 ms，記憶體約為 368 kB，通過測試。如果要複製 vector 資料再另一個 vector，可以使用 algorithm 函式庫的 copy，語法為

copy(來源v1資料起點, 來源v1資料終點, 目標v2起點);

如果確定目標容器 v2 的長度足夠，可以用

v2.begin()

如果不確定目標容器 v2 的長度是否足夠，可以用

back_inserter(v2)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;  // n 張牌，洗牌 m 次
    while(cin >> n >> m) {
        vector<int> deck (n);  // 讀取牌面數值
        for(int i=0; i<n; i++) cin >> deck[i];
        vector<int> upp (deck.begin(), deck.begin() + n/2), bot (deck.begin()+n/2, deck.end());  // 分成上、下兩半
        for(int i=0; i<m; i++) {  // 執行 m 次
            for(int j=0; j<n/2; j++) {  // 執行 n/2 次
                deck[2*j] = upp[j];  // 從 upp 及 bot 依序取值放入 deck
                deck[2*j+1] = bot[j];
            }
            copy(deck.begin(), deck.begin() + n/2, upp.begin());  // 更新 upp、bot
            copy(deck.begin() + n/2, deck.end(), bot.begin());
        }
        for(int i=0; i<n; i++) cout << deck[i] << " \n"[i == n-1];  // 印出答案
    }
    return 0;
}

寫法2，滾動陣列，將洗牌後的資料先存入另一個陣列。使用時間約為 3 ms，記憶體約為 372 kB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;  // n 張牌，洗牌 m 次
    while(cin >> n >> m) {
        vector<int> deck (n), tmp (n);  // 讀取牌面數值，暫存洗牌後的資料
        for(int i=0; i<n; i++) cin >> deck[i];
        for(int i=0; i<m; i++) {  // 執行 m 次
            for(int j=0; j<n/2; j++) {  // 執行 n/2 次
                tmp[2*j] = deck[j];  // 從 deck 前半取值放入 tmp
                tmp[2*j+1] = deck[n/2 + j];  // 從 deck 後半取值放入 tmp
            }
            swap(deck, tmp);  // 交換 deck、tmp
        }
        for(int i=0; i<n; i++) cout << deck[i] << " \n"[i == n-1];  // 印出答案
    }
    return 0;
}