Trung vị của k phần tử

Points: 3 (partial)

Time limit: 1.0s

JAVA11 2.0s

Python 3 2.0s

Memory limit: 500M

Author:

hoanbabe_cute19

Problem type

Bạn được cho một dãy số nguyên gồm n phần tử. Nhiệm vụ của bạn là tính trung vị của mỗi cửa sổ gồm k phần tử tính từ trái qua phải.

Biết trung vị là số ở chính giữa khi mà các phần tử đã được sắp xếp. Nếu số phần tử là chẵn,

sẽ có 2 trung vị có thể xảy ra nhưng mặc định trong bài toán này chugns ta sẽ lấy phần tử có giá trị nhỏ hơn là trung vị.

Ví dụ có dãy số sau gồm 4 phần tử: 1 2 4 5 thì 2 sẽ là trung vị.

Đầu vào

Dòng đầu sẽ lần lượt là 2 số nguyên n và k: số phần tử của dãy và kích thước của của sổ (\( 1 \le k \le n \le 2\) * \(10^5\))

Dòng thứ 2 chứa một dãy \(n\) số nguyên \(a_1, a_2, ..., a_n\)

Đầu ra

In ra 1 dòng gồm n - k + 1 giá trị trung vị cần tìm, mỗi số cách nhau bởi 1 dấu cách

Ví dụ

Đầu vào:

8 3
2 4 3 5 8 1 2 1

Đầu ra:

3 4 5 5 2 1

Comments

LãoTam commented on Dec. 28, 2023, 3:40 p.m. ← edited →

Ahihi

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for(ll i = 0; i < n; i++) {
        cin >> a[i];
    }
    multiset<ll> w(a.begin(), a.begin() + k);
    auto mid = next(w.begin(), k / 2);
    for(ll i = k; ; i++) {
        cout << (k % 2 ? *mid : *prev(mid)) << ' ';
        if(i == n)
            break;
        w.insert(a[i]);
        if(a[i] < *mid)
            mid--;
        if(a[i - k] <= *mid)
            mid++;
        w.erase(w.lower_bound(a[i - k]));
    }
    cout << endl;
    return 0;
}