ค้นหาต้นทุนสูงสุดของอาร์เรย์คู่โดยเลือกคู่ K มากที่สุดใน C++

สมมติว่าเรามีอาร์เรย์ของคู่ A; เราต้องหาต้นทุนสูงสุดในการเลือกคู่ K ให้ได้มากที่สุด ในกรณีนี้ ค่าใช้จ่ายของอาร์เรย์ขององค์ประกอบประเภทคู่เป็นผลคูณของผลรวมขององค์ประกอบแรกของคู่ที่เลือกและน้อยที่สุดในบรรดาองค์ประกอบที่สองของคู่ที่เลือก ตัวอย่างเช่น หากเลือกคู่เหล่านี้ (4, 8) (10, 3) และ (3, 6) ต้นทุนจะเป็น (4+10+3)*(3) =51 สำหรับ K=3

ดังนั้น หากอินพุตเป็น A =[(15, 5), (65, 25), (35, 20), (20, 5), (35, 20), (15, 18), (3, 8 ), (12, 17)], K =4 แล้วเอาท์พุตจะเป็น 2700

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• res :=0, sum =0

• N :=ขนาด A

• กำหนดคู่หนึ่งชุดที่เรียกว่า my_set

• จัดเรียงอาร์เรย์ A ตามค่าที่สองของแต่ละคู่

• สำหรับการเริ่มต้น i :=N - 1 เมื่อ i>=0, อัปเดต (ลด i โดย 1) ให้ทำ -

  • สร้างคู่ (องค์ประกอบแรกของ A[i], i) และแทรกลงใน my_set

  • sum :=sum + องค์ประกอบแรกของ A[i]

  • ในขณะที่ขนาดของ my_set> K ทำ -

    • มัน :=องค์ประกอบแรกของ my_set

    • sum :=sum - ก่อนอื่นเลย

    • ลบออกจาก my_set

  • res :=สูงสุดของ res และ sum * วินาทีของ A[i]

• ผลตอบแทน

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include ใช้เนมสเปซ std;bool compactor (const pair&a,const pair&b) { return (a.second > &A, int K){ int res =0, sum =0; int N =A.size(); set> my_set; sort(A.begin(), A.end(), รถบดอัด); สำหรับ (int i =N - 1; i>=0; --i) { my_set.insert(make_pair(A[i].first, i)); ผลรวม +=A[i].first; ในขณะที่ (my_set.size()> K) { อัตโนมัติ =my_set.begin(); ผลรวม -=it->ก่อน; my_set.erase(มัน); } res =max(res, ผลรวม * A[i].second); } return res;}int main() { vector> arr ={{ 15, 5}, { 65, 25}, { 35, 20}, { 20, 5}, { 35, 20 }, { 15, 18}, { 3, 8 }, {12, 17}}; int K =4; ศาล < 
อินพุต
 <ก่อน>{{15, 5},{65, 25}, { 35, 20}, { 20, 5}, { 35, 20}, { 15, 18}, { 3, 8}, {12, 17 }}, 4

ผลลัพธ์

2700