Giả sử chúng ta có bốn số nguyên a, b, c và k. Ta phải tìm giá trị dương nhỏ nhất x sao cho phương trình sau thỏa mãn -
𝑎𝑥2+𝑏𝑥+𝑐 ≥𝑘
Nếu a =3, b =4, c =5 và k =6, thì đầu ra sẽ là 1
Để giải quyết điều này, chúng ta sẽ sử dụng phương pháp phân giác. Giới hạn dưới sẽ là 0 vì x phải là số nguyên dương tối thiểu.
Ví dụ
#include<iostream> using namespace std; int getMinX(int a, int b, int c, int k) { int x = INT8_MAX; if (k <= c) return 0; int right = k - c; int left = 0; while (left <= right) { int mid = (left + right) / 2; int val = (a * mid * mid) + (b * mid); if (val > (k - c)) { x = min(x, mid); right = mid - 1; } else if (val < (k - c)) left = mid + 1; else return mid; } return x; } int main() { int a = 3, b = 2, c = 4, k = 15; cout << "Minimum value of x is: " << getMinX(a, b, c, k); }
Đầu ra -
Minimum value of x is: 2