Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | sdo.in, sdo.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  Andrei Misarca •Mishu91 |
| Timp execuţie pe test | 0.6 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Statistici de ordine
A i-a statistică de ordine a unei mulţimi este al i-lea cel mai mic element al mulţimi. Fiind date o mulţime de numere naturale A, de N elemente şi un număr natural K, să se determine a K-a statistică de ordine a mulţimii.
Date de intrare
Fişierul de intrare sdo.in conţine pe prima linie N şi K, iar pe a doua linie N numere naturale, reprezentând elementele mulţimii A.
Date de ieşire
În fişierul de ieşire sdo.out se va afla un singur număr natural, reprezentând a K-a statistică de ordine a mulţimii.
Restricţii
- 1 ≤ K ≤ N ≤ 3 000 000
- Toate cele N elemente ale mulţimii A sunt din intervalul [1, 109]
Exemplu
| sdo.in | sdo.out |
|---|---|
| 8 3 1 10 4 13 7 6 11 14 | 6 |
Explicaţie
În exemplu, se observă că elementele aranjate în ordine crescătoare sunt: 1 4 6 7 10 11 13 14, prin urmare al 3-lea cel mai mic element este 6.
O primă soluţie, care numără pentru fiecare element câte elemente sunt mai mici decât el, având complexitatea de 
, şi ar trebui să obţină 10 puncte.
O altă soluţie care selectează cele mai mici K elemente, având complexitatea 
obţine în jur de 20 puncte.
Altă soluţie care sortează elementele în ordine crescătoare şi are complexitatea 
ar trebui să obţină 50 puncte.
O altă soluţie, cu complexitatea 
, care foloseşte un heap pentru a menţine cele mai mici K elemente ar trebui să obţină 60 puncte. O soluţie care obţine tot 60 de puncte este cea de complexitate 
. Deşi complexitatea este teoretic mai bună, ea se comportă mai slab decât cea menţionată anterior, datorită folosirii unei structuri care rulează mai încet, priority_queue.
O soluţie care sortează elementele în timp aproape liniar, folosind radix sort ar trebui să obţină în jur de 70 de puncte.
Soluţia cea mai eficientă foloseşte funcţia de partiţionare a quicksort-ului pentru a determina a K-a statistică de ordine. Practic, acest algoritm este foarte asemănător quicksort-ului, doar că în loc să se sorteze tot şirul se vor sorta doar anumite porţiuni care ajută la determinarea soluţiei. Însă această soluţie obţine 90 de puncte. Pentru 100 de puncte se va folosi un pivot ales aleator, în loc de un pivot fixat. Complexitatea acestui algoritm este în medie 
, însă teoretic în cel mai defavorabil caz poate atinge pentru că am putea fi extrem de nenorocoşi să partiţionăm în jurul celui mai mare element rămas. Dar deoarece algoritmul este aleator, nu există date de intrare particulare care să provoace comportamentul celui mai defavorabil caz, acesta fiind motivul pentru care algoritmul care selectează pivotul random este mai eficient decât cel care selectează un pivot fixat. Acest algoritm este implementat şi în STL, funcţia nth_element găsindu-se în headerul algorithm. O sursă demonstrativă se găseşte aici. Există şi un algoritm teoretic ce garantează pe cel mai defavorabil caz, care se poate găsi în Cormen la capitolul "Statistici de Ordine".
