Program C++ untuk mencari jumlah minimum yang diperlukan untuk melanggan perkhidmatan OTT

Andaikan operator telekom melancarkan perkhidmatan yang dipanggil "semua-dalam-satu" yang menyediakan akses kepada n pembekal kandungan OTT pada harga tetap sebanyak k USD. Sekarang, jika kami perlu melanggan platform OTT secara langsung, kami perlu membayar yuran berasingan untuk setiap platform. Kami tidak perlu melanggan setiap platform sepanjang bulan, jadi kami perlu mencari cara untuk menggunakan perkhidmatan mereka secara efektif. Kami memerlukan bulan permulaan perkhidmatan untuk platform yang saya berikan dalam array start_month dan bulan berakhir yang diberikan dalam array end_month. Harga yang diperlukan untuk melanggan platform diberikan dalam harga tatasusunan[i]. Kami perlu mengetahui jumlah minimum yang perlu kami bayar untuk melanggan semua platform mengikut keperluan kami.

Jadi jika input adalah seperti n = 3, k = 10, start_month = {1, 2, 1}, end_month = {3, 3, 2}, price = {5, 7, 8}, maka output akan menjadi 30

Kami perlu melanggan perkhidmatan selama 3 bulan.

Untuk bulan pertama, kami perlu melanggan platform 1 dan 3. Kos $5 + 8 = $13 setiap satu, tetapi dengan pakej "semua dalam satu" ia berharga $10 USD sahaja. Begitu juga, bulan kedua, kami memerlukan ketiga-tiganya, dengan jumlah kos $20. Tetapi kami membayar $10 untuk ketiga-tiga mereka. Pada bulan ketiga, jumlah kos langganan menjadi $12, tetapi kami hanya membayar $10.

Jadi, jumlah kos ialah 10 + 10 + 10 = 30.

Langkah

Untuk menyelesaikan masalah ini kami akan mengikuti langkah berikut -

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

Contoh

Mari kita lihat pelaksanaan berikut untuk pemahaman yang lebih baik -

#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

Atas ialah kandungan terperinci Program C++ untuk mencari jumlah minimum yang diperlukan untuk melanggan perkhidmatan OTT. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!