Descriere:
Se dă un vector h[1..n], Mao taie din fiecare bambus ce depășește înălțimea H, pentru a totaliza cel puțin M metri. Să se găsească maximul H posibil.
Categorie: vector + căutare binară (și sumă parțială)
Algoritm:
Problema este o funcție monotonă: pentru un H mai mic, suma obținută S(H) crește.
Aplicăm căutare binară pe H în intervalul [0, max(h)].
Pentru un H dat, se calculează eficient S(H), sumând doar valorile tăiate.
Complexitate: O(n log max).
Link: #250 Interclasare1
Descriere:
Două șiruri ordonate strict crescător (a, b). Se cere reuniunea sub forma unui șir strict crescător, fără duplicate.
Algoritm:
Folosește doi indici, i (pe a), j (pe b).
Avansezi comparând a[i] și b[j], inseri valoarea mai mică, sau una singură în caz de egalitate.
După terminarea unuia dintre șiruri, se adaugă restul elementelor celuilalt.
Complexitate: O(n + m).
Descriere:
Se dă un vector de n numere; în formă binară, se cere lungimea maximă a unei secvențe de biți 1 (adică, lungimea maximă a unei părți care, în formă binară, are doar cifra 1).
Algoritm:
Se transformă fiecare element în formă binară: fără conversie explicită, putem folosi operații bitwise.
Parcurgem vectorul, menținem cur = 0 când apare un element ce NU este format doar din biți 1, altfel cur++.
Comparăm cu best după fiecare increment.
Complexitate: O(n * log v) (dar pentru valori mici, este eficient).
Descriere:
Se dă un vector de n numere; se cere cea mai lungă secvență care începe și se termină cu aceeași valoare. Dacă sunt mai multe de aceeași lungime, se alege prima.
Algoritm:
Parcurgere în două bucle sau cu hash:
Pentru fiecare poziție i, extinzi j spre dreapta până întâlnești același v[i], actualizezi best.
Variantă eficientă: păstrezi într-un hash (sau vector auxiliar) ultima poziție a fiecărei valori întâlnite.
La pasul j, secvența de la first_index[val] la j este candidată.
Complexitate: O(n) cu structuri adecvate.
1
Bambusi
Alege H maxim pentru tăiere≥M
Căutare binară + sumă parțială
2
Interclasare1
Reuniunea dintre două șiruri crescătoare, fără duplicate
Interclasare (merge), complexitate O(n+m)
3
Secventa11
Lungime maximă a secvenței de elemente cu toți biții 1
Parcurgere + verificare bitwise
4
SecvEgale1
Cea mai lungă secvență care începe și se termină cu aceeași valoare
Parcurgere cu mapare poziții + O(n)