โปรแกรม C++ เพื่อค้นหาจำนวนเงินขั้นต่ำที่จำเป็นในการสมัครบริการ OTT

สมมติว่าผู้ให้บริการโทรคมนาคมรายหนึ่งได้แนะนำบริการที่เรียกว่า "all-in-one" ซึ่งให้การเข้าถึงผู้ให้บริการเนื้อหา n OTT ในราคาคงที่ที่ k ดอลลาร์ ตอนนี้ หากเราต้องสมัครใช้งานแพลตฟอร์ม OTT โดยตรง เราต้องจ่ายค่าธรรมเนียมเป็นรายบุคคลให้กับแต่ละแพลตฟอร์ม เราไม่จำเป็นต้องสมัครสมาชิกกับทุกแพลตฟอร์มทุกเดือน ดังนั้นเราจึงต้องหาวิธีการใช้บริการของพวกเขาอย่างคุ้มค่า เดือนเริ่มต้นที่เราต้องการบริการของแพลตฟอร์ม i จะได้รับในอาร์เรย์ start_month และเดือนที่สิ้นสุดจะได้รับในอาร์เรย์ end_month ราคาที่จำเป็นในการสมัครแพลตฟอร์มจะได้รับในราคาอาร์เรย์[i] เราต้องหาจำนวนเงินที่น้อยที่สุดที่เราต้องจ่ายเพื่อสมัครใช้งานแพลตฟอร์มทั้งหมดตามความต้องการของเรา

ดังนั้น หากอินพุตเป็น n =3, k =10, start_month ={1, 2, 1}, end_month ={3, 3, 2}, ราคา ={5, 7, 8} ผลลัพธ์จะเป็น 30

เราต้องการสมัครใช้บริการเป็นเวลา 3 เดือน

ในเดือนแรก เราจำเป็นต้องมีการสมัครสมาชิกสำหรับแพลตฟอร์ม 1 และ 3 แยกกัน มีค่าใช้จ่ายทั้งหมด 5 + 8 =13 ดอลลาร์ แต่สำหรับแพ็คเกจ "all-in-one" จะมีค่าใช้จ่าย 10 ดอลลาร์เท่านั้น ในทำนองเดียวกันในเดือนที่สอง เราต้องการทั้งสามอย่างซึ่งมีราคารวม 20 ดอลลาร์ แต่เราจ่าย 10 สำหรับทั้งสาม และในเดือนที่สาม ค่าใช้จ่ายทั้งหมดสำหรับการสมัครสมาชิกจะกลายเป็น 12 ดอลลาร์ แต่เราจ่ายเพียง 10 เหรียญเท่านั้น

ดังนั้น ค่าใช้จ่ายทั้งหมดคือ 10 + 10 + 10 =30

ขั้นตอน

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

Define an array pairArray
for initialize i := 0, when i < n, update (increase i by 1), do:
   insert pair(start_month[i], price[i]) at the end of pairArray
   insert pair(end_month[i] + 1, -price[i]) at the end of pairArray
sort the array pairArray
pre := 0
c := 0
res := 0
for each element p in pairArray, do:
   day := first element of p - pre
   res := res + minimum of (k, c)
   c := c + second element of p
pre := first element of p
return res

ตัวอย่าง

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

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

vector<vector<int>> G;
vector<int> res;

int solve(int n, int k, int start_month[], int end_month[], int price[]){
   vector<pair<int, int>> pairArray;
   for(int i = 0; i < n; i++) {
      pairArray.push_back(make_pair(start_month[i], price[i]));
      pairArray.push_back(make_pair(end_month[i] + 1, -price[i]));
   }
   sort(pairArray.begin(), pairArray.end());
   int pre = 0;
   int c = 0;
   int res = 0;
   for(auto p : pairArray) {
      int day = p.first - pre;
      res += min(k, c) * day;
      c += p.second; pre = p.first;
   }
   return res;
}
int main() {
   int n = 3, k = 10, start_month[] = {1, 2, 1}, end_month[] = {3, 3, 2}, price[] = {5, 7, 8};
   cout<< solve(n, k, start_month, end_month, price);
   return 0;
}

อินพุต

3, 10, {1, 2, 1}, {3, 3, 2}, {5, 7, 8}