解題說明
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],做法如何調整?
- 如果有多組合法解,如何枚舉所有可能?