Question

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

Answer 1

#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; }

Answer 2

Am o solutie in care se foloseste STL - ul ...sper sa te ajute :

#include <bits/stdc++.h>
#define MAX_N 4000005
using namespace std;
unsigned int v[MAX_N], n, k, i;

int main()
{
    freopen ("statisticiordine.in","r",stdin);
    ofstream g("statisticiordine.out");
    scanf("%d %d", &n, &k);
    for(i = 1; i <= n; i ++)
        scanf("%ul", &v[i]);
    nth_element(v + 1, v + k, v + n + 1);
    g << v[k];
    return 0;
}