Truy vấn trung vị - LCOJ: Luyện Code Online Judge

MEDIAN - Truy vấn trung vị

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Bạn được cho một dãy ~n~ số nguyên dương không giảm và ~m~ truy vấn, với mỗi truy vấn bạn được yêu cầu in ra phần tử trung vị của dãy hiện tại và loại bỏ nó khỏi dãy (nếu dãy có ~n~ số theo thứ tự không giảm thì số trung vị là số thứ ~[\frac{n + 1}{2}]~).

Input

Dòng đầu chứa hai số nguyên dương ~n~ và ~m~;
Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, …, a_n~ được liệt kê theo thứ tự không giảm.

Giới hạn:

~1 ≤ m ≤ n ≤ 10^6; 1 ≤ a_i ≤ 10^9~.

Output

Ghi ra trên một dòng kết quả ~m~ truy vấn, hai số liên tiếp cách nhau một dấu cách.

Sample

Input #1

5 4
1 2 3 3 5

Output #1

3 2 3 1

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.

include <bits/stdc++.h>

using namespace std;

int main(){ ios::syncwithstdio(false); cin.tie(nullptr);

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

stack<int> left, right;
int mid = (n + 1) / 2;
// left: a[0..mid-1], right: a[mid..n-1], in reverse order for right
for(int i = 0; i < mid; i++){
    left.push(a[i]);
}
for(int i = n - 1; i >= mid; i--){
    right.push(a[i]);
}

vector<int> res;
res.reserve(m);

for(int i = 0; i < m; i++){
    // median is top of left
    res.push_back(left.top());
    left.pop();
    // re-balance: if right has more, move one
    if(!right.empty() && right.size() > left.size()){
        left.push(right.top());
        right.pop();
    }
}

// in kết quả
for(int i = 0; i < res.size(); i++){
    if(i) cout << ' ';
    cout << res[i];
}
cout << '\n';
return 0;

}

SuperCoder đã bình luận lúc 19, Tháng 10, 2025, 14:03 ← chỉnh sửa →

Lời giải cho mọi người tham khảo nha

#include <bits/stdc++.h>


using namespace std;

int main() {
    ios::syncwithstdio(false);
    cin.tie(nullptr);
    int n,m; cin >> n >> m;
    vector<int> v(n);

    for(int i = 0; i < n; i++) cin >> v[i];
    // O(n)
    /*
    for(int i = 0; i < m; i++) {
        int mid = ((v.size()+1) / 2)-1;
        cout << v[mid] << " ";
        v.erase(v.begin() + mid);
    }
    */
    // dùng stack
    stack<int> left, right;
    int mid = (n+1)/2;
    for(int i = 0; i < mid; i++) left.push(v[i]);
    for(int i = n - 1; i >= mid; --i) right.push(v[i]);
    for(int i = 0; i < m; i++) {
        cout << left.top() << " ";
        left.pop();
        if(right.size() > left.size()) {
            left.push(right.top());
            right.pop();
        }
    }
    return 0;
}