Tìm K mục có giá trị nhỏ nhất trong C++

Cho danh sách (tên, giá trị) và số k. Nhiệm vụ: tìm K mục có giá trị nhỏ nhất.

Mô tả: Lấy k mục có giá trị nhỏ nhất từ danh sách.

Ví dụ:

Đầu vào: items = { {item1, 200}, {item2, 100}, {item3, 500}, {item4, 400} }, k = 2

Đầu ra: item1, item2

Giải thích:

Hai mục giá trị nhỏ nhất: item2 (100), item1 (200).

Phương pháp giải

Sắp xếp danh sách theo giá trị tăng dần. Lấy k phần tử đầu.

Chương trình minh họa

Ví dụ

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

bool compVal(pair<string, int> A, pair<string, int> B) {
    if (A.second == B.second)
        return A.first < B.first;
    return A.second < B.second;
}

int main() {
    int k = 2;
    int n = 3;
    vector<pair<string, int> > items;
    items.push_back(make_pair("item1", 350));
    items.push_back(make_pair("item2", 150));
    items.push_back(make_pair("item3", 500));
    items.push_back(make_pair("item4", 100));
    sort(items.begin(), items.end(), compVal);
    cout << k << " items with least value are \n";
    for (int i = 0; i < min(n, k); ++i)
        cout << "Item : " << items[i].first << ", value : " << items[i].second << endl;
    return 0;
}

Kết quả

2 items with least value are Item : item4, value : 100 Item : item2, value : 150