OTTサービスに加入するために必要な最小金額を見つけるためのC++プログラム

ある通信事業者が「オールインワン」と呼ばれるサービスを導入したとします。このサービスは、kドルの固定価格でn個のOTTコンテンツプロバイダーへのアクセスを提供します。現在、OTTプラットフォームに直接加入する必要がある場合は、各プラットフォームに個別の料金を支払う必要があります。すべての月にすべてのプラットフォームのサブスクリプションを必要としないため、費用対効果の高い方法でそれらのサービスを使用する方法を見つける必要があります。プラットフォームiのサービスが必要な開始月は配列start_monthで指定され、終了月は配列end_monthで指定されます。プラットフォームにサブスクライブするために必要な価格は、アレイ価格[i]で示されます。要件に従って、すべてのプラットフォームにサブスクライブするために支払う必要のある最小金額を見つける必要があります。

したがって、入力がn =3、k =10、start_month ={1、2、1}、end_month ={3、3、2}、price ={5、7、8}の場合、出力は次のようになります。 30

3か月間のサービスのサブスクリプションが必要です。

最初の月には、プラットフォーム1と3のサブスクリプションが必要です。個別に、合計5 + 8 =13ドルですが、「オールインワン」パッケージでは10ドルしかかかりません。同様に、2か月目には、3つすべてが必要になります。合計で20ドルかかります。しかし、3つすべてに10を支払います。そして、3か月目には、サブスクリプションの合計コストは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}

出力

30