解題說明
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），找最大行數？