UVa 10935 - 拋棄卡片模擬隊列操作

問題描述

有一副編號 1 到 n 的卡片，重複以下操作：丟棄最頂端的卡片，將新的最頂端卡片移到底部，直到只剩一張卡片。輸出被丟棄的卡片順序和最後剩下的卡片。

解法：隊列模擬

使用隊列完美模擬該過程：

1. 將 1 到 n 入隊。
2. 當隊列大小 > 1 時，出隊並記錄為丟棄卡片，再出隊並將該卡片入隊（移到底部）。
3. 最後隊列中剩下的即為剩餘卡片。

注意輸出格式：丟棄卡片之間用逗號分隔，首個前無逗號；n=1 時無丟棄卡片。

代碼實現（Java）

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (true) {
            int n = in.nextInt();
            if (n == 0) break;
            Queue q = new LinkedList<>();
            for (int i = 1; i <= n; i++) q.offer(i);
            System.out.print("Discarded cards:");
            boolean first = true;
            while (q.size() > 1) {
                if (first) { System.out.print(" " + q.poll()); first = false; }
                else System.out.print(", " + q.poll());
                q.offer(q.poll());
            }
            System.out.println();
            System.out.println("Remaining card: " + q.poll());
        }
    }
}

複雜度分析

時間複雜度 O(n)，空間複雜度 O(n)。n 最大未給出，但隊列模擬完全足夠。