解題說明
Arranging Coins
題目描述:你有 n 枚硬幣,要將它們排成階梯形狀:第 1 行放 1 枚,第 2 行放 2 枚,... 第 k 行放 k 枚。找出可以完整排滿的最大行數 k。
解題思路:需要找最大 k 使得 k*(k+1)/2 <= n。二分搜尋法:在 [1, n] 上二分搜尋,對每個中間值 mid 計算 mid*(mid+1)/2,若 <= n 則向右縮,否則向左縮,最終 lo-1 或 hi 即為答案。數學公式法:解二次方程 k² + k - 2n = 0,得 k = (-1 + sqrt(1 + 8n)) / 2,取整即得。注意使用 long long 防止溢位。
C++ 解法
複雜度分析
時間複雜度:O(log n) — 二分搜尋在 [1, n] 區間上執行。
空間複雜度:O(1) — 只使用常數個變數。
虛擬碼
1. Set lo = 1, hi = n 2. While lo <= hi: a. mid = lo + (hi - lo) / 2 b. coins = mid * (mid + 1) / 2 c. If coins == n: return mid d. If coins < n: lo = mid + 1 e. Else: hi = mid - 1 3. Return hi
其他解法
數學公式(O(1)):解方程式 k² + k - 2n = 0,利用求根公式 k = (int)((-1 + sqrt(1 + 8.0*n)) / 2)。此法為常數時間,最為高效,但需注意浮點精度,可在結果上驗證並調整 ±1。
線性掃描(O(√n)):從 k=1 開始不斷累加,直到 sum > n,回傳 k-1。雖然簡單直觀,但對大 n 效率較差。
延伸思考
- 如果改為三角形(第 i 行放 i 枚),如何用數學公式直接計算?
- 若 n 非常大(超過 long long),應如何處理?
- 如何將此問題推廣為:每行放的硬幣數為等差數列(首項為 a,公差為 d),找最大行數?