C++程序以查找订阅OTT服务所需的最少金额

WBOY 转载: 2023-09-07 23:37:02 380浏览

假设一家电信运营商推出了一项名为“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;
}