解題說明
Find Missing Observations
題目描述：
有 n + m 次骰子擲出結果，已知 m 次的結果陣列 rolls 和所有結果的平均值 mean。求 n 次缺失的骰子結果，使得所有 n + m 次的平均值恰好為 mean。若無合法解則回傳空陣列。
解題思路：
- 計算缺失的
n個骰子的總和：missingSum = mean * (n + m) - sum(rolls)。 - 檢查是否有合法解：每個骰子的值在 1 到 6 之間，因此
missingSum必須滿足n <= missingSum <= 6 * n。 - 分配值：先讓所有
n個骰子都取missingSum / n，餘數missingSum % n個骰子各多加 1。
C++ 解法
複雜度分析
時間複雜度：O(n + m) — 計算已知總和 O(m)，建構結果 O(n)。
空間複雜度：O(n) — 結果陣列大小為 n。
虛擬碼
1. Compute knownSum = sum of rolls 2. Compute missingSum = mean * (n + m) - knownSum 3. If missingSum < n or missingSum > 6*n: return [] 4. Set base = missingSum / n, extra = missingSum % n 5. Create result array of n elements, all set to base 6. Add 1 to the first 'extra' elements 7. Return result
其他解法
貪心逐一分配 O(n)：每次為一個骰子分配盡可能接近平均值的數字，同時確保剩餘的骰子仍能湊出合法總和。邏輯稍複雜但結果相同。
隨機化法 O(n)：隨機產生骰子值，最後調整使總和吻合。不保證最優分布但可以通過。
延伸思考
- 如果要求輸出字典序最小的結果，如何修改分配策略？
- 如果骰子不是標準 1-6 面，而是任意範圍 [a, b]，做法如何調整？
- 如果有多組合法解，如何枚舉所有可能？