Programme C++ pour trouver le montant minimum requis pour souscrire à un service OTT

Supposons qu'un opérateur de télécommunications lance un service appelé « tout-en-un » qui donne accès à n fournisseurs de contenu OTT à un prix fixe de k USD. Désormais, si nous devons nous abonner directement aux plateformes OTT, nous devons payer des frais distincts à chaque plateforme. Nous n'avons pas besoin de nous abonner à chaque plateforme pendant tous les mois, nous devons donc trouver un moyen d'utiliser leurs services de manière rentable. Nous avons besoin du mois de début du service pour la plate-forme que j'ai indiqué dans le tableau start_month et du mois de fin indiqué dans le tableau end_month. Le prix nécessaire pour souscrire à la plateforme est indiqué dans le tableau price[i]. Nous devons connaître le montant minimum que nous devons payer pour nous abonner à toutes les plateformes selon nos besoins.

Donc, si l'entrée est quelque chose comme n = 3, k = 10, start_month = {1, 2, 1}, end_month = {3, 3, 2}, price = {5, 7, 8}, alors la sortie aura 30 ans

Nous devons nous abonner au service pendant 3 mois.

Pour le premier mois, nous devons nous abonner aux plateformes 1 et 3. Coûte 5 $ + 8 = 13 $ chacun, mais avec le forfait « tout en un », cela ne coûte que 10 $ USD. De même, le deuxième mois, nous avons besoin des trois, pour un coût total de 20$. Mais nous avons payé 10 $ pour ces trois-là. Le troisième mois, le coût total de l'abonnement devient 12$, mais nous ne payons que 10$.

Donc, le coût total est de 10 + 10 + 10 = 30.

Étapes

Pour résoudre ce problème, nous suivrons les étapes suivantes -

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

Exemple

Voyons l'implémentation suivante pour une meilleure compréhension -

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

Input

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

Output

30

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!