Trimovana medijana

Data je sekvenca celih brojeva \(a_1, a_2, \ldots, a_n\) i ceo broj \(t\) (\(0 \leq t < n / 2\)). Najpre izbacujemo tačno \(t\) najmanjih i tačno \(t\) najvećih elemenata po vrednosti (u slučaju jednakih vrednosti, izbacuje se onoliko elemenata koliko je potrebno da ukupno izbačenih bude \(t\) sa dna i \(t\) sa vrha). Od preostalih elemenata treba pronaći donju medijanu: element koji bi stajao na poziciji \(\lfloor \frac{m + 1}{2} \rfloor\) kada bismo preostale elemente sortirali neopadajuće.

Za maksimalno poena rešiti zadatak u prosečnoj vremenskoj složenosti \(O(n)\).

Opis ulaza

Sa standardnog ulaza se unosi broj elemenata niza \(n\) (\(1 \leq n \leq 10^6\)) i broj najmanjih i najvećih elemenata \(t\) (\(0 \leq t < n / 2\)), koje treba ukloniti iz niza.

Opis izlaza

Nakon uklanjanja \(t\) najmanjih i \(t\) najvećih elemenata niza, na standardni izlaz ispisati donju medijanu.

Primer 1

Ulaz

Izlaz

Objašnjenje

Sortiran niz je [1, 2, 2, 3, 5, 8, 9], nakon uklanjanja jednog najvećeg i jednog najmanjeg elementa niza, niz postaje [2, 2, 3, 5, 8]. Donja medijana je 3.

Primer 2

Ulaz

Izlaz

Objašnjenje

Sortiran niz je [1, 1, 4, 4, 4, 4, 10, 100], nakon uklanjanja dva najveća i dva najmanja elementa niza, niz postaje [4, 4, 4, 4]. Donja medijana je 4.

Rešenje

Opis glavnog rešenja

U ovom bloku se opisuje glavno rešenje zadatka.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() 
{
    int n, t; cin >> n >> t;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int m = n - 2 * t;
    int r = (m + 1) / 2;
    int ind = t + r - 1;
    
    nth_element(a.begin(), a.begin() + ind, a.end());

    cout << a[ind] << endl;

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

int partition(vector<int> &a, const int l, const int r)
{
    int i = l + 1, j = r;
    while (i <= j) {
        if (a[i] < a[l]) {
            i++;
        } else if (a[j] > a[l]) {
            j--;
        } else {
            swap(a[i++], a[j--]);
        }
    }
    swap(a[l], a[j]);

    return j;
}

int quickselect(vector<int> &a, const int k)
{
    int l = 0, r = a.size() - 1;
    while (l <= r) {
        int p = partition(a, l, r);
        if (p < k - 1) {
            l = p + 1;
        } else if (p > k - 1) {
            r = p - 1;
        } else {
            return a[p];
        }
    }

    assert(false);
    return -1;
}

int main() 
{
    int n, t; cin >> n >> t;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int m = n - 2 * t;
    int r = (m + 1) / 2;
    int ind = t + r;
    
    cout << quickselect(a, ind) << endl;

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() 
{
    int n, t; cin >> n >> t;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    int m = n - 2 * t;
    int r = (m + 1) / 2;
    int ind = t + r - 1;
    
    cout << a[ind] << endl;

    return 0;
}