441.排列硬币

题目来源：力扣https://leetcode.cn/problems/arranging-coins/

题目简介：

公差为1的等差数列，第一排放1，第二排放2……求给出一个n值，最多可以放几排。

思路：

假设最多可以排列n行，x是第n行的硬币个数，那么每行排列的硬币个数分别为 1 2 3 4 … x；同时n为每行硬币相加之和 (即满足n=1+2+3+4+…+x)，也就是说从1到n行，会存在一个x值，使得等式1+2+3+ … +x=n成立，因此我们可以通过使用二分法从1到n行定位到那个x值。

代码实现：

class Solution {
public:
    int arrangeCoins(int n) {
        int left = 1, right = n;
        while (left < right) {
            int mid = (right - left + 1) / 2 + left;
            if ((long long) mid * (mid + 1) <= (long long) 2 * n) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};