Căutare binară pe răspuns
Căutarea binară pe răspuns este o tehnică care transformă o problemă de optimizare (“găsește valoarea maximă/minimă X pentru care…”) într-o problemă de decizie (“este posibil cu valoarea X?”), pe care o rezolvă apoi prin căutare binară.
E una dintre cele mai puternice tehnici în programare competitivă - o vei întâlni la olimpiade, concursuri și probleme clasice.
Ideea
De obicei, căutarea binară caută o valoare într-un vector sortat. Dar uneori “vectorul” nu există fizic - îl “imaginăm”: e mulțimea răspunsurilor posibile.
Condiția cheie: monotonie
Pentru a aplica căutarea binară pe răspuns, trebuie să existe
un prag critic k*:
- Pentru orice
x >= k*→ răspunsul e “DA, posibil” - Pentru orice
x < k*→ răspunsul e “NU, imposibil”
(sau invers, în funcție de problemă)
x: 1 2 3 4 5 6 7 8 9 10
check: N N N N D D D D D D
↑
k* = 5 (cel mai mic x care merge)Dacă funcția de check e monotonă (NU… NU…
DA… DA…), putem găsi k* în O(log(rang)) apeluri la
check.
Problema clasică: Bookshelves
Enunțul
Avem n cărți cu lățimile w[1..n].
Le așezăm în ordine pe k rafturi (raft după raft,
pe o singură linie). Vrem să găsim lățimea
minimă a unui raft, astfel încât toate cărțile să
încapă pe cele k rafturi.
Cărți: [3, 5, 2, 8, 4, 1], k = 3
Cu lățimea raftului = 10:
Raft 1: 3 + 5 + 2 = 10
Raft 2: 8
Raft 3: 4 + 1 = 5
OK
Cu lățimea raftului = 9:
Nu merge (nu poti pune cartea de 8 cu 3+5=8)
Lățime minimă = 10Strategia
Fixăm x = lățimea raftului. Verificăm în O(n)
dacă încap toate cărțile în k rafturi. Dacă da,
x e posibil. Dacă nu, trebuie mai mare.
Funcția check:
bool check(int x, int k) {
int rafturi = 1, curent = 0;
for (int i = 0; i < n; i++) {
if (w[i] > x) return false; // o carte e mai lata decat raftul
if (curent + w[i] > x) {
rafturi++;
curent = w[i];
} else {
curent += w[i];
}
}
return rafturi <= k;
}Căutarea binară cu
st <= dr
- Minimul posibil al lățimii:
max(w[i])(cartea cea mai largă trebuie să încapă) - Maximul posibil: suma tuturor (toate cărțile pe un raft)
Păstrăm o variabilă rasp cu cel mai bun răspuns
găsit până acum:
int st = *max_element(w, w + n);
int dr = accumulate(w, w + n, 0);
int rasp = dr; // un raspuns valid initial (maximul sigur merge)
while (st <= dr) {
int mij = st + (dr - st) / 2;
if (check(mij)) {
rasp = mij; // salvam - mij e un raspuns valid
dr = mij - 1; // cautam unul mai mic
} else {
st = mij + 1; // mij e prea mic
}
}
cout << rasp; // latimea minimaComplexitate: O(n log S), unde S = suma lățimilor.
Cod complet
#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int w[100001];
int n, k;
bool check(int x)
{
int rafturi = 1, curent = 0;
for (int i = 0; i < n; i++) {
if (w[i] > x) return false;
if (curent + w[i] > x) {
rafturi++;
curent = w[i];
} else {
curent += w[i];
}
}
return rafturi <= k;
}
int main()
{
fin >> n >> k;
int st = 0, dr = 0;
for (int i = 0; i < n; i++) {
fin >> w[i];
if (w[i] > st) st = w[i];
dr += w[i];
}
int rasp = dr;
while (st <= dr) {
int mij = st + (dr - st) / 2;
if (check(mij)) {
rasp = mij;
dr = mij - 1;
} else {
st = mij + 1;
}
}
fout << rasp;
return 0;
}date.in:
6 3
3 5 2 8 4 1date.out:
10Șablonul general
Căutarea binară pe răspuns cu
while (st <= dr) are o structură
standard unică, indiferent dacă vrem minim sau maxim.
Diferența e doar ce salvăm și în ce direcție
restrângem.
Șablonul
pentru MINIM (cel mai mic x care merge)
int st = MIN_RASPUNS;
int dr = MAX_RASPUNS;
int rasp = -1; // sau o valoare sentinela
while (st <= dr) {
int mij = st + (dr - st) / 2;
if (check(mij)) {
rasp = mij; // mij e valid - il salvam
dr = mij - 1; // incercam sa gasim unul mai mic
} else {
st = mij + 1; // mij nu merge, incercam mai mare
}
}
cout << rasp; // cel mai mic x care mergeȘablonul
pentru MAXIM (cel mai mare x care merge)
int st = MIN_RASPUNS;
int dr = MAX_RASPUNS;
int rasp = -1;
while (st <= dr) {
int mij = st + (dr - st) / 2;
if (check(mij)) {
rasp = mij; // mij e valid - il salvam
st = mij + 1; // incercam sa gasim unul mai mare
} else {
dr = mij - 1; // mij nu merge, incercam mai mic
}
}
cout << rasp; // cel mai mare x care mergeAvantajul acestui șablon: e simetric, nu
depinde de cum incrementezi mij, iar variabila
rasp păstrează mereu cel mai bun răspuns valid
găsit.
Problema 2: aggressive cows
Ai n boxe pe o linie (pozițiile
x[1..n], sortate crescător) și vrei să plasezi
c vaci astfel încât distanța
minimă între oricare două vaci să fie
maximă.
Boxe: 1, 2, 4, 8, 9, 10
c = 3
Distanța minimă maximă = 5 (pozițiile 1, 4, 10 - distanțele 3 și 6, minim 3)
Pentru pozitiile 1, 4, 10 distantele sunt 3, 6 - minim 3
Pentru pozitiile 1, 4, 9 distantele sunt 3, 5 - minim 3
...Strategia
Fixăm distanța minimă d. Putem plasa cele
c vaci astfel încât toate perechile să aibă
distanță >= d?
Greedy: plasează prima vacă în prima boxă. Apoi, pentru fiecare boxă nouă, dacă distanța față de ultima vacă e >= d, plasează o vacă acolo.
bool check(int d) {
int plasate = 1;
int ultima = x[0];
for (int i = 1; i < n; i++) {
if (x[i] - ultima >= d) {
plasate++;
ultima = x[i];
}
}
return plasate >= c;
}Căutăm cel mai mare d care
merge (deci folosim varianta pentru MAXIM):
int st = 1, dr = x[n-1] - x[0];
int rasp = -1;
while (st <= dr) {
int mij = st + (dr - st) / 2;
if (check(mij)) {
rasp = mij;
st = mij + 1;
} else {
dr = mij - 1;
}
}
cout << rasp;Când să aplici căutarea binară pe răspuns?
Semne că problema cere această tehnică:
1. “Cea mai mare/mică valoare astfel încât…”
- “Cel mai mic raft astfel încât cărțile să încapă în k rafturi”
- “Cea mai mare distanță minimă”
- “Numărul minim de zile pentru a termina”
2. Funcția check e mai ușoară decât optimizarea directă
Uneori direct e greu să calculezi optimul, dar să verifici dacă o valoare fixă merge e simplu.
3. Răspunsul e într-un domeniu mărginit
Știi un minim și un maxim pentru răspuns (rang
[st, dr]). Căutarea binară face
O(log(dr - st)) iterații.
Problema 3: koko eating bananas
Există n grămezi de banane v[i].
Koko mănâncă cu viteza k banane/oră. Într-o oră,
mănâncă din o singură grămadă - dacă grămada e
mai mică decât k, termină grămada și așteaptă ora
următoare.
Găsește viteza minimă k astfel
încât Koko să termine toate grămezile în h ore.
Grămezi: [3, 6, 7, 11], h = 8
k = 4: 3/4=1h, 6/4=2h, 7/4=2h, 11/4=3h → 1+2+2+3 = 8h ✓
k = 3: 1+2+3+4 = 10h ✗
Răspuns: 4Soluție
bool check(int k) {
long long ore = 0;
for (int i = 0; i < n; i++)
ore += (v[i] + k - 1) / k; // ceil(v[i] / k)
return ore <= h;
}
int st = 1, dr = *max_element(v, v + n);
int rasp = dr;
while (st <= dr) {
int mij = st + (dr - st) / 2;
if (check(mij)) {
rasp = mij;
dr = mij - 1;
} else {
st = mij + 1;
}
}
cout << rasp;Pas cu pas: Bookshelves
Cărți [3, 5, 2, 8, 4, 1],
k = 3.
- Minim: max = 8
- Maxim: suma = 23
raspinițial = 23
Iterație 1: st=8, dr=23, mij = 15
Check(15): 3+5+2=10 (raft 1), 8+4+1=13 (raft 2) → 2 rafturi <= 3 ✓ → rasp = 15, dr = 14
Iterație 2: st=8, dr=14, mij = 11
Check(11): 3+5+2=10 (raft 1), 8=8 (raft 2), 4+1=5 (raft 3) → 3 rafturi <= 3 ✓ → rasp = 11, dr = 10
Iterație 3: st=8, dr=10, mij = 9
Check(9): 3+5=8 (raft 1), 2+8 nu >9, 2=2 (raft 2), 8=8 (raft 3), 4+1=5 (raft 4) → 4 > 3 ✗ → st = 10
Iterație 4: st=10, dr=10, mij = 10
Check(10): 3+5+2=10, 8, 4+1=5 → 3 rafturi ✓ → rasp = 10, dr = 9
st=10 > dr=9, ieșim
Răspuns: rasp = 10
Greșeli frecvente
1. Funcția check nu e monotonă
Dacă valorile “DA/NU” sunt amestecate
(NU, DA, NU, DA), nu poți aplica
căutarea binară.
Verifică mereu: dacă x merge, toate valorile mai
mari/mici (după caz) merg?
2. Limitele inițiale greșite
int st = 0; // GRESIT pentru bookshelves - cartea de 8 nu incape pe raft de 0
int st = max(w); // CORECTGândește-te la minimul și maximul posibil al răspunsului.
3. Uitarea actualizării
lui rasp
// GRESIT - uitam rasp = mij
while (st <= dr) {
int mij = st + (dr - st) / 2;
if (check(mij)) dr = mij - 1;
else st = mij + 1;
}
// rasp e necunoscut!
// CORECT - salvam in rasp valoarea valida
while (st <= dr) {
int mij = st + (dr - st) / 2;
if (check(mij)) { rasp = mij; dr = mij - 1; }
else st = mij + 1;
}4. Overflow la mij
int mij = (st + dr) / 2; // poate depasi int daca st, dr sunt mari
int mij = st + (dr - st) / 2; // mai sigur - nu overflow-eaza5. Confundarea x
cu indicele
Nu confunda valoarea căutată (răspunsul) cu indicele într-un
vector. La căutare binară pe răspuns,
mij nu e un indice într-un vector,
ci o valoare candidată.
Tabel exemple
| Problema | Ce căutăm | Funcția check |
|---|---|---|
| Bookshelves | min lățime raft | cărțile încap în k rafturi? |
| Aggressive cows | max distanță minimă | putem plasa c vaci la distanța >= d? |
| Koko bananas | min viteză | mâncăm totul în <= h ore? |
| Split array | min suma maximă | putem împărți în <= k părți? |
| Rope cutting | max lungime bucată | putem tăia >= c bucăți de lungime x? |
Complexitate
Pentru un răspuns în intervalul [1, R]:
- Căutarea binară: O(log R) iterații
- Fiecare iterație cheamă
checkîn O(f(n)) - Total: O(f(n) * log R)
De obicei, check e liniar O(n),
deci total O(n log R).
Ce să reții
- Căutarea binară pe răspuns transformă optimizare în decizie + căutare binară.
- Condiție: funcția
check(x)trebuie să fie monotonă (toate DA-urile împreună, toate NU-urile împreună). - Determină st și dr din contextul problemei.
- Folosim șablonul
while (st <= dr)și păstrăm cel mai bun răspuns înrasp.- Pentru minim: dacă check reușește,
rasp = mij; dr = mij - 1 - Pentru maxim: dacă check reușește,
rasp = mij; st = mij + 1
- Pentru minim: dacă check reușește,
- Exemple clasice: bookshelves, aggressive cows, koko bananas, split array.
- Complexitate tipică: O(n log R).