ค้นหารายการ K ที่มีค่าต่ำสุดใน C++

ในปัญหานี้ เราได้รับรายการที่ประกอบด้วยรายการและค่าของรายการและจำนวนเต็ม k งานของเราคือ ค้นหารายการ K ที่มีค่าต่ำสุด

คำอธิบายปัญหา: เราต้องหา k รายการจากรายการที่มีค่าต่ำสุด

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล: item-value ={ {item1, 200}, {item2, 100}, {item3, 500}, {item4, 400}} k =2

ผลลัพธ์: item1 , item2

คำอธิบาย:

2 องค์ประกอบที่มีค่าน้อยที่สุดคือ item1 ที่มี 200 และ item2 ที่มีค่า 100

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาคือการหาสิ่งของ k ที่มีค่าน้อยที่สุดอย่างตะกละตะกลาม ก่อนอื่นเราจะเรียงลำดับรายการตามลำดับค่าจากน้อยไปมาก จากรายการที่จัดเรียงนี้ เราจะพบ k รายการที่มีมูลค่าน้อยที่สุด

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#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;
}

ผลลัพธ์

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