/**[二分查找][简单]
你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
给定一个数字 n，找出可形成完整阶梯行的总行数。
n 是一个非负整数，并且在32位有符号整型的范围内。
示例 1:
n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整，所以返回2.
示例 2:
n = 8
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因为第四行不完整，所以返回3.
*/

/*
个人感悟：
第一种思路好想，主要考虑边界条件，第二种思路不好想，但代码简单，执行效率高。
疑惑：
本题和二分查找有什么关系？存在利用二分查找的更好解法？
*/

/*
思路1：逐行累加硬币个数，总和超过给定硬币数，说明符合条件的行数为当前行数减一
注意：总数sum的类型为long防止用例给INT_MAX为硬币数,导致int溢出
*/
class Solution {
public:
    int arrangeCoins(int n) {
        int k = 0;
        long sum = 0;
        while(sum <= n){
            k++;
            sum += k;
        }
        return k-1;
    }
};
/*
思路2：从等差数列求和公式想到，将图形颠倒合并可拼成一个矩形，则k*(k+1)=2n，利用一元二次等式求解公式可得答案。
*/
class Solution {
public:
    int arrangeCoins(int n) {
        return sqrt(n*2.0 + 0.25) - 0.5;
    }
};