Chương trình C ++ để tìm ra số tiền ít nhất cần thiết để đăng ký các dịch vụ OTT

Giả sử, một nhà khai thác viễn thông đã giới thiệu một dịch vụ gọi là "tất cả trong một" cung cấp quyền truy cập vào n nhà cung cấp nội dung OTT với mức giá cố định là k đô la. Bây giờ, nếu chúng tôi phải đăng ký trực tiếp vào các nền tảng OTT, chúng tôi phải trả một khoản phí riêng cho từng nền tảng. Chúng tôi không cần đăng ký cho mọi nền tảng vào tất cả các tháng, vì vậy chúng tôi phải tìm cách sử dụng hiệu quả chi phí dịch vụ của họ. Tháng bắt đầu mà chúng tôi cần dịch vụ của nền tảng i được đưa ra trong mảng start_month và tháng kết thúc được đưa ra trong mảng end_month. Giá cần thiết để đăng ký một nền tảng được đưa ra trong giá mảng [i]. Chúng tôi phải tìm ra số tiền ít nhất mà chúng tôi phải trả để đăng ký tất cả các nền tảng theo yêu cầu của chúng tôi.

Vì vậy, nếu đầu vào là n =3, k =10, start_month ={1, 2, 1}, end_month ={3, 3, 2}, price ={5, 7, 8}, thì đầu ra sẽ là 30

Chúng tôi cần đăng ký dịch vụ trong 3 tháng.

Trong tháng đầu tiên, chúng tôi cần đăng ký cho nền tảng 1 và 3. Riêng chúng, chúng có giá tổng cộng là 5 + 8 =13 đô la, nhưng với gói "tất cả trong một", chi phí chỉ là 10 đô la. Tương tự như vậy trong tháng thứ hai, chúng tôi cần cả ba cái với tổng giá 20 đô la. Nhưng chúng tôi trả 10 cho cả ba. Và trong tháng thứ ba, tổng chi phí cho các đăng ký là 12 đô la, nhưng chúng tôi chỉ phải trả 10 đô la.

Vì vậy, tổng chi phí là 10 + 10 + 10 =30.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

30