Hướng tiếp cận

Tiếp cận 1 : Vét cạn, sử dụng while mỗi lần sẽ cộng thêm 1 giá trị của K lặp đến khi tổng lớn hơn thì thoát

Tiếp cận 2 : Dùng thuật toán tìm kiếm nhị phân : Chặt tìm vị trí k thoả điều kiện

Code C++ tối ưu (Tìm kiếm nhị phân)

#include <iostream>
using namespace std;

long long maxK(long long n) {
    long long left = 1, right = 2e5, ans = 1;
    while (left <= right) {
        long long mid = (left + right) / 2;
        if (mid * (mid + 1) / 2 <= n) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return ans;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        long long n;
        cin >> n;
        cout << maxK(n) << endl;
    }
    return 0;
}

Tiếp cận 3: Sử dụng công thức

1. Tổng của ~ k ~ số tự nhiên đầu tiên:

~ S = \frac{k \times (k+1)}{2} ~ Để xếp đủ các tầng, tổng số vật phẩm ~ S ~ không được vượt quá ~ n ~: ~ \frac{k \times (k+1)}{2} \leq n ~

2. Chuyển đổi bất đẳng thức:

Nhân cả hai vế với 2: ~ k \times (k+1) \leq 2 \times n ~ Mở rộng và sắp xếp lại ta có: ~ k^2 + k - 2n \leq 0 ~

3. Giải phương trình bậc hai:

Đây là phương trình bậc hai dạng: ~ k^2 + k - 2n = 0 ~ Áp dụng công thức nghiệm của phương trình bậc hai: ~ k = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} ~ Thay các giá trị:

• ~ a = 1 ~
• ~ b = 1 ~
• ~ c = -2n ~

~ k = \frac{-1 \pm \sqrt{1^2 - 4 \times 1 \times (-2n)}}{2 \times 1} ~

Rút gọn lại ta có: ~ k = \frac{-1 \pm \sqrt{1 + 8n}}{2} ~

4. Chọn nghiệm dương:

Chỉ lấy nghiệm dương vì ~ k ~ biểu thị số tầng (phải là số nguyên dương): ~ k = \frac{-1 + \sqrt{1 + 8n}}{2} ~