h1(#triangles). 'Triangles':problema/triangles

h1(#triangles). 'Triangles':problema/triangles
Pentru inceput sa analizam modul in care ar trebui sa arate cele K laturi selectate.Sa le notam cu x1,x2,...,xK,unde x1<=x2<=...<=xK.Conditia necesara pentru ca 3 numere a,b,c sa reprezinte laturile unui triunghi (chiar si degenerat) este ca a+b>=c,a+c>=b si a+b>=c. Daca presupunem a<=b<=c,atunci singura conditie necesara de verificat va fi a+b>=c. Acum sa ne reintoarcem la selectia noastra de K laturi. Pentru ca selectia sa fie valida trebuie doar ca suma celor mai mici 2 laturi sa fie mai mare decat cea mai mare latura,adica x1+x2>=xK.
1.Solutia O(N*log N) care nu se incadreaza in timp ar fi sortarea sirului de N laturi + parcurgerea lui pentru verificarea conditiei de mai sus pentru fiecare subsecventa de lungime K.
2.Solutia O(N*log K) care ia 100pct este aceea de a citi primele K numere dintre cele N,a le pune intr-un min-heap (retinand si elementul maxim din el intr-o variabila) si verificarea conditiei.Daca conditia este verificata atunci afisez elementele din heap,altfel scot minimul din heap,citesc un nou numar,il introduc in heap actualizand elementul maxim din heap din variabila auxiliara si continui verificarea pana gasesc o solutie de afisat.