Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-11-29 19:46:34.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:sdo.in, sdo.outSursăArhiva educationala
AutorArhiva EducationalaAdăugată deMishu91Andrei Misarca Mishu91
Timp execuţie pe test0.6 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

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.insdo.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 O(N^2), şi ar trebui să obţină ... puncte.

Altă soluţie care sortează elementele în ordine crescătoare şi are complexitatea O(Nlog_{2}N) ar trebui să obţină 70 puncte.

O altă soluţie, cu complexitatea O(Nlog_{2}K), care foloseşte un heap pentru a menţine cele mai mici K elemente ar trebui să obţină 70 puncte.

În final, soluţia care ar trebui să obţină 100 de puncte 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. 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. Complexitatea acestui algoritm este în medie O(N), dar în cel mai defavorabil caz poate atinge O(N^2)

Marius Nu ar fi mai bine ca O(N2) 20p, O(N logN) 50p, O(N logK) 60-70, O(N) 100? Când atinge O(N2) algoritmul O(N)?
Paul: Parca am citit pe undeva ca nth_element din STL are complexitatea worst case O(NlogN). E si suspect sa mearga sort-ul worst case O(NlogN) si statisticile de ordine O(N^2). Verifica acest fapt.

Aplicaţii

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?