目录

lc441.排列硬币

Shen 收录于每日一题

2021-10-10 约 162 字预计阅读 1 分钟

目录

441.排列硬币

二分查找

1-k行求和相当于等差数列求和s=(k+1)k/2
目的是求出来最后一个行的和小于等于n的行。
注意会爆int
$T:O(n)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
public:
    int arrangeCoins(int n) {
        int l = 1, r = n;
        if(n == 1)  return 1;
        // 找最后一个小于等于n的数
        while(l < r) {
            int mid = (r - l + 1 >> 1) + l;
            if((long long) mid * (mid + 1) <= n * 2ll) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }

        return l;
    }
};