LeetCode 1739. 放置盒子（推公式）

思路：
最終一定是按照下面這樣排列，方格上的數字代表這個位置可以壘多高，

圖1

圖2

所以假設底面放的數目為 m i d mid mid：
先按照 ( N + 1 ) ? N / 2 = m i d (N+1)*N/2=mid (N+1)?N/2=mid算出N，也就是圖一中的梯形圖的高度，
那么結果就是 ∑ i = 1 N ( i + 1 ) ? i 2 \sum_{i=1}^N\frac{(i+1)*i}{2} ∑i=1N?2(i+1)?i?，
還剩下一部分是 n u m 2 = m i d ? ( N + 1 ) ? N / 2 num2=mid-(N+1)*N/2 num2=mid?(N+1)?N/2，這一部分填在梯形圖外圍，如圖二所示，最終貢獻就是 ( n u m 2 + 1 ) ? n u m 2 2 \frac{(num2+1)*num2}{2} 2(num2+1)?num2?，

typedef long long ll;
class Solution {
public:
    int cal(int x) {
        return 1ll * (1ll * x * (x + 1) * (2 * x + 1) + 1ll * (1 + x) * x * 3) / 12;
    }
    bool check(int n,int mid) {
        int N = (-1 + sqrt(1 + 8 * mid)) / 2;
        int m = (1 + N) * N / 2;
        int num2 = (mid - m + 1) * (mid - m) / 2;
        int num = cal(N) + num2;
        return num >= n;
    }
    int minimumBoxes(int n) {
        int l = 1,r = min(1650467,n);
        int ans = min(n,1650467);
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(check(n,mid)) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
};