Ở đây chúng ta sẽ thấy một bài toán thú vị, chúng ta sẽ tìm một cặp (x, y), trong đó x và y nằm trong khoảng nên l <=x, y <=r, cặp này sẽ có một thuộc tính, giá trị của x chia cho y . Nếu có nhiều cặp có sẵn, thì chỉ chọn một cặp.
Chúng ta có thể giải quyết vấn đề này trong thời gian O (1), nếu chúng ta nhận được giá trị của giới hạn dưới l và 2l. Chúng ta biết rằng giá trị nhỏ nhất của y / x có thể là 2 và nếu một giá trị lớn hơn nào đó nằm trong phạm vi thì giá trị 2 sẽ nằm trong phạm vi đó. Và nếu chúng ta tăng x, nó cũng sẽ tăng gấp 2 lần, vì vậy l và 2l sẽ là cặp nhỏ nhất nằm trong khoảng đã cho.
Ví dụ
#include<iostream>
using namespace std;
void getPair(int l, int r) {
int x = l;
int y = 2 * l;
cout << "(" << x << ", " << y << ")" << endl;
}
int main() {
int l = 3, r = 6;
getPair(l, r);
} Đầu ra
(3, 6)