Cerința

Se dau n numere naturale. Să se afișeze al k-ulea cel mai mic element din șir.

Date de intrare

Fișierul de intrare statisticiordine.in conține pe prima linie numerele n si k, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire statisticiordine.out va conține pe prima linie numărul căutat.

Restricții și precizări

1 ≤ k ≤ n ≤ 4.000.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 4.000.000.000

Exemplu

statisticiordine.in

6 4
1 58 4 3 24 50

statisticiordine.out

Explicație

24 este al patrulea cel mai mic element din sir.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema StatisticiOrdine:

#include <fstream>
#include <stdlib.h>
#include <time.h>

#define MAX_N 4000000

unsigned v[MAX_N];

unsigned quickSelect(int l, int r, int k) {
  if (l == r) {
    return v[l];
  }
  int i = l, j = r;
  unsigned piv = v[rand() % (r - l + 1) + l];

  while (i <= j) {
    while (v[i] < piv) {
      i++;
    }
    while (v[j] > piv) {
      j--;
    }
    if (i <= j) {
      int tmp = v[i];
      v[i] = v[j];
      v[j] = tmp;
      i++;
      j--;
    }
  }
  if (k <= (j - l + 1)) {
    return quickSelect(l, j, k);
  } else {
    return quickSelect(j + 1, r, k - (j - l + 1));
  }
}

int main(void) {
  int n, k;
  std::fstream f("statisticiordine.in", std::ios::in);

  f >> n >> k;
  for (int i = 0; i < n; i++) {
    f >> v[i];
  }
  f.close();

  srand(time(0));

  f.open("statisticiordine.out", std::ios::out);
  f << quickSelect(0, n - 1, k) << '\n';
  f.close();
  return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1264 StatisticiOrdine

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1264 StatisticiOrdine de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1264 StatisticiOrdine