ค้นหาจำนวนเต็มบวกขั้นต่ำ x ที่ a(x^2) + b(x) + c>=k ใน C++

สมมติว่าเรามีจำนวนเต็มสี่จำนวน a, b, c และ k เราต้องหาค่าบวกขั้นต่ำ x เพื่อให้สมการต่อไปนี้เป็นไปตาม −

𝑎𝑥2+𝑏𝑥+𝑐 ≥𝑘

ถ้า a =3, b =4, c =5 และ k =6 ผลลัพธ์จะเป็น 1

เพื่อแก้ปัญหานี้ เราจะใช้วิธีการสองส่วน ขีดจำกัดล่างจะเป็น 0 เนื่องจาก x ต้องเป็นจำนวนเต็มบวกขั้นต่ำ

ตัวอย่าง

#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);
}

ผลลัพธ์ -

Minimum value of x is: 2