Codeforces 509C Sums of Digits 詳解

題目：給定嚴格遞增正整數序列 a₁..aₙ（已丟失），僅知其數位和序列 b₁..bₙ (1≤bᵢ≤300)。要求重構 a 序列，使 aₙ 盡可能小（字典序最小等價）。n≤300。

核心思想：貪心逐位構造，保證前綴最小

從 a₁ 到 aₙ 依次構造。對於 aᵢ，已知 aᵢ₋₁ 且需 aᵢ > aᵢ₋₁ 且 digitSum(aᵢ) = bᵢ。要使最終 aₙ 最小，每一步都應使 aᵢ 盡可能小（貪心最優子結構）。

單個數構造：給定下界 L 且數位和 S，求最小滿足條件的數

將 L 與目標數對齊（高位補 0）。從低位向高位枚舉「修改位」：

1. 保持高位不變，在某位 pos 將數字增大（d > L[pos]），低位填最小數字使總和達標。
2. 枚舉 pos 從低到高（優先修改低位，影響較小），d 從 L[pos]+1 到 9。
3. 檢查剩餘低位能否湊出所需和：need = S - (高位和) - d，需滿足 0 ≤ need ≤ 9*pos。
4. 低位填充策略：從最低位開始盡量放 9，最後一位放餘數（確保數值最小）。

算法流程

1. a₁：直接構造數位和為 b₁ 的最小正整數（低位堆 9）。
2. 對於 i=2..n：
   設 prev = aᵢ₋₁ 的數位陣列（低位在前）。
   維護 prefix_sum = 高位已固定部分的數位和。
   枚舉修改位 pos = 0..max_len：
     更新 prefix_sum（減去原 pos-1 位）。
     枚舉新數字 d = prev[pos]+1 .. 9：
       add = d - prev[pos]，new_sum = prefix_sum + add。
       若 new_sum ≤ bᵢ ≤ new_sum + 9*pos → 可行。
       構造低位：rem = bᵢ - new_sum，低位貪心放 9。
       高位 pos+1.. 保持與 prev 相同。
       得到候選 aᵢ，跳出循環。
     若所有 pos 都不可行（理論上不會），增加位數（高位補 1，低位構造）。

參考代碼邏輯 (C++)

// 核心函數：給定前一個數 prev_digits[], 目標和 target, 返回最小的下一個數
vector construct_next(const vector& prev, int target) {
    int len = prev.size();
    vector cur(len, 0);
    int prefix_sum = accumulate(prev.begin(), prev.end(), 0);
    for (int pos = 0; pos <= len; ++pos) { // pos 為修改位，允許擴展新位
        if (pos > 0) prefix_sum -= prev[pos-1];
        int start_d = (pos < len) ? prev[pos] + 1 : 1; // 新位從 1 開始
        for (int d = start_d; d <= 9; ++d) {
            int new_sum = prefix_sum + d;
            int low_pos = pos; // 低位個數
            if (new_sum <= target && target <= new_sum + 9 * low_pos) {
                // 可行，構造
                int rem = target - new_sum;
                // 低位貪心放 9
                for (int i = 0; i < low_pos; ++i) {
                    cur[i] = min(9, rem);
                    rem -= cur[i];
                }
                cur[pos] = d;
                // 高位複製 prev
                for (int i = pos+1; i < len; ++i) cur[i] = prev[i];
                // 去除前導零（高位）
                while (cur.size() > 1 && cur.back() == 0) cur.pop_back();
                return cur;
            }
        }
    }
    // 理論上不可達，題目保證有解
    return {};
}

關鍵細節

• 數位陣列低位在前：便於處理進位與擴展位數。
• 前綴和動態維護：枚舉 pos 時減去 pos-1 位，O(1) 更新。
• 可行性判斷：new_sum ≤ target ≤ new_sum + 9*pos，低位能否湊足餘量。
• 低位填充最小化數值：從最低位放 9，使高位盡可能小（如 19 < 91）。
• 擴展位數：當 pos == len 時，表示需增加一位（如 999 → 1999）。

複雜度分析

總結

CF 509C 是「貪心構造 + 數位 DP 思想」的精妙結合。它展示了如何在「嚴格遞增 + 數位和約束」下，通過從低位向高位嘗試修改，構造字典序最小的序列。核心技巧：保持高位不變、在最低可能位增大、低位貪心填 9。此模式適用於「給定下界求最小滿足數位屬性的數」等問題（如 LeetCode 1085、數位 DP 類）。