โปรแกรมค้นหาจำนวนแพ็คเกจสูงสุดที่ผู้ซื้อสามารถซื้อได้ใน C++

สมมติว่าเรามีรายการขายและผู้ซื้อสองรายการ แต่ละองค์ประกอบในการขายประกอบด้วยสองค่าในรูปแบบ [วัน, ราคา] ซึ่งบ่งชี้ว่าแพ็คเกจพร้อมขายเฉพาะในวันนั้นสำหรับราคาที่กำหนด และแต่ละองค์ประกอบในผู้ซื้อในรูปแบบ [payday, amount] แสดงว่าผู้ซื้อมีเงินจำนวนนั้นที่จะใช้จ่ายในวันจ่ายเงินเดือนและหลังจากนั้น หากผู้ซื้อแต่ละรายสามารถซื้อได้ไม่เกินหนึ่งแพ็คเกจ และแต่ละแพ็คเกจสามารถขายให้กับบุคคลได้เพียงคนเดียว ให้หาจำนวนแพ็คเกจสูงสุดที่สามารถซื้อได้

ดังนั้น ถ้า input เหมือนกับ sales =[[0, 5], [0, 5], [0, 6], [1, 4], [1, 5], [3, 4]] ผู้ซื้อ =[[ 0, 4], [0, 6],[1, 5]] จากนั้นผลลัพธ์จะเป็น 3 เนื่องจากคนแรกสามารถรับแพ็คเกจ [1, 4] คนที่สองสามารถรับ [0, 6] และคนสุดท้ายรับพัสดุได้ [1, 5]

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

• ยกเลิก :=0

• จัดเรียงผู้ซื้ออาร์เรย์ตามวันจ่ายเงิน ถ้าวันจ่ายเงินเหมือนกัน เรียงลำดับตามจำนวนเงิน

• กำหนดชุด pq

• เรียงลำดับการขายอาร์เรย์

• ผม :=0

• สำหรับแต่ละรายการในการขาย -

  • ในขณะที่ (i <ขนาดของผู้ซื้อและผู้ซื้อ[i, 0] <=มัน[0]), ทำ −

    • แทรกผู้ซื้อ[i, 1] ลงใน pq

    • (เพิ่ม i ขึ้น 1)

  • j :=ดัชนีของ pq เพื่อแทรก [i] intp pq และทำให้เรียงลำดับ

  • ถ้า j เป็นดัชนีที่ถูกต้อง −

    • (เพิ่มการถอยกลับโดย 1)

    • ลบองค์ประกอบ jth ออกจาก pq

• รีเทิร์น

ตัวอย่าง

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

#include ใช้เนมสเปซ std;class Solution { public:static bool cmp(vector&a, vector&b) { return a[0] ==b[0 ] ? a[1]> b[1] :a[0] >&sales, vector>&ผู้ซื้อ) { int ret =0; เรียงลำดับ(buyers.begin(), buyer.end()); มัลติเซ็ต pq; sort(sales.begin(), sales.end(), cmp); int ผม =0; สำหรับ (อัตโนมัติ&มัน:การขาย) { ในขณะที่ (ผม <ผู้ซื้อขนาด() &&ผู้ซื้อ[i][0] <=มัน[0]) { pq.insert(ผู้ซื้อ[i][1]); ผม++; } auto j =pq.lower_bound(มัน[1]); ถ้า (j !=pq.end()) { ret++; pq.erase(j); } } ส่งคืน ret; }};int แก้ (vector>&sales, vector>&ผู้ซื้อ) { return (new Solution())->solve(sales, ผู้ซื้อ);}int main(){ vector <เวกเตอร์> ยอดขาย ={{0, 5},{0, 5},{0, 6},{1, 4},{1, 5},{3, 4}}; vector<เวกเตอร์> ผู้ซื้อ ={{0, 4},{0, 6},{1, 5}}; cout <<แก้ (ขาย, ผู้ซื้อ);}

อินพุต

ผลลัพธ์

3