C++程式以尋找訂閱OTT服務所需的最少金額-C++-PHP中文網

C++程式以尋找訂閱OTT服務所需的最少金額

WBOY

發布： 2023-09-07 23:37:02

轉載

708 人瀏覽過

C++程式以尋找訂閱OTT服務所需的最少金額

假設一家電信業者推出了一項名為「all-in-one」的服務，該服務以k 美元的固定價格提供對n 個OTT 內容提供商的訪問。現在，如果我們必須直接訂閱OTT平台，我們必須向每個平台支付單獨的費用。我們不需要在所有月份訂閱每個平台，因此我們必須找到一種經濟高效地使用他們的服務的方法。我們需要平台 i 的服務的起始月份在數組 start_month 中給出，結束月份在數組 end_month 中給出。訂閱平台所需的價格在陣列price[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 美元，但使用「一體式」套餐則花費 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;
}

登入後複製