Codeforces Good Bye 2013 B題：New Year Present - 貪心構造機器人指令序列

Codeforces Good Bye 2013 B題：New Year Present - 貪心構造機器人指令序列

題目大意

n 個錢包排成一排，第 i 個需要放入 a[i] 個硬幣。機器人初始站在最左邊（位置 1），每秒可執行三種操作之一：

• L：向左移動一格（若不在最左端）
• R：向右移動一格（若不在最右端）
• P：在當前位置放入一枚硬幣

限制：不能連續執行兩次 P 操作。總操作數不超過 10^6。輸出任意合法操作序列。

核心觀察與貪心策略

由於不能連續 P，當某位置需要放入多枚硬幣（a[i] > 1）時，必須在兩次 P 之間插入移動操作。最簡策略：

• 非邊界位置：使用 RL 或 LR 往返（如 PRLP）
• 最右端（位置 n）：只能用 LR（先左後右）
• 最左端（位置 1）：只能用 RL（先右後左）

算法流程

1. 從左到右遍歷每個位置 i = 1..n
2. 對於位置 i，放入 a[i] 枚硬幣：
   • 第一枚直接 P
   • 第 2 到第 a[i] 枚：根據邊界情況插入 RL 或 LR 再 P
3. 若非最後一個位置，執行 R 移動到下一個位置

完整 AC 代碼

#include <iostream>
#include <cstdio>
using namespace std;

int a[305];

int main() {
    int n;
    while (cin >> n) {
        for (int i = 0; i < n; i++) cin >> a[i];
        
        for (int i = 0; i < n; i++) {
            int placed = 0;  // 當前位置已放入硬幣數
            while (a[i] > 0) {
                if (placed > 0) {
                    // 第2枚及以後，需要插入移動避免連續P
                    if (i == n - 1) cout << "LR";  // 最右端：先左後右
                    else cout << "RL";             // 其他：先右後左
                }
                cout << "P";
                a[i]--;
                placed++;
            }
            if (i < n - 1) cout << "R";  // 移動到下一個位置
        }
        cout << endl;
    }
    return 0;
}

樣例解析

輸入：2\n1 2

輸出：PRPLRP

• 位置 1：P（放1枚）→ R（移到位置2）
• 位置 2：P（第1枚）→ LR（往返）→ P（第2枚）

輸入：4\n0 2 0 2

輸出：RPRRPLLPLRRRP

複雜度與正確性證明

• 時間複雜度：O(n + Σa[i])，每個硬幣常數次操作
• 操作數上界：Σa[i] * 3 + n ≤ 300 * 300 * 3 + 300 = 270,300 < 10^6，滿足限制
• 邊界處理正確：最右端用 LR、最左端用 RL 保證不越界
• 無連續 P：每兩個 P 間至少插入 2 個移動指令