Tìm số nhỏ thứ K trong mảng - LCOJ: Luyện Code Online Judge

AQUERY2 - Tìm số nhỏ thứ K trong mảng

Đ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

Có một dãy số ban đầu rỗng. Người ta lần lượt thực hiện ~Q~ thao tác. Ở thao tác thứ ~i~, người ta sẽ chèn thêm ~b_i~ số có giá trị ~a_i~ vào cuối dãy số.

Sau khi thực hiện xong cả ~Q~ thao tác, hãy cho biết số nhỏ thứ K trong dãy có giá trị bao nhiêu.

Input

Dòng đầu tiên gồm số nguyên ~Q\ (1 ≤ Q ≤ 10^5)~ - số thao tác được thực hiện;
~Q~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~a_i~ và ~b_i~ ~(1 ≤ a_i, b_i ≤ 10^9)~ - mô tả thao tác thứ ~i~;
Dòng tiếp theo gồm số nguyên ~K\ (1 ≤ K ≤ b_1 + b_2 + . . . + b_Q)~.

Output

In ra giá trị số nhỏ thứ ~K~ sau khi thực hiện ~Q~ thao tác.

Sample

Input #1

Output #1

Input #2

4 7 1 1 1 4 1 4 1 3



#### Output #2



#### Input #3

1 100 1 1



#### Output #3

100 ```

Hint

Ở ví dụ thứ nhất, dãy số thu được là ~[5, 5, 2, 2, 2, 3]~. Giá trị nhỏ thứ 4 trong dãy này là ~3~;
Ở ví dụ thứ hai, dãy số thu được là ~[7, 1, 4, 4]~. Giá trị nhỏ thứ ~3~ trong dãy này là ~4~;
Ở ví dụ thứ ba, dãy số thu được là ~[100]~. Giá trị nhỏ nhất trong dãy này cũng là ~100~.

Problem source: Kc97ble - Free Contest

Bình luận

Please read the guidelines before commenting.

kietjumper đã bình luận lúc 3, Tháng 1, 2026, 16:14 ← chỉnh sửa →

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

vector< pair< int, int > > a;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int p, q;
        cin >> p >> q;
        a.push_back({p, q});
    }
    int k;
    cin >> k;
    sort(a.begin(), a.end());
    for (auto i : a)
    {
        if (k - i.second > 0) k -= i.second;
        else
        {
            cout << i.first;
            return 0;
        }
    }
}