OTT 서비스 가입에 필요한 최소 금액을 찾는 C++ 프로그램-C++-php.cn

OTT 서비스 가입에 필요한 최소 금액을 찾는 C++ 프로그램

WBOY

풀어 주다： 2023-09-07 23:37:02

앞으로

711명이 탐색했습니다.

OTT 서비스 가입에 필요한 최소 금액을 찾는 C++ 프로그램

통신 사업자가 k USD의 고정 가격으로 n OTT 콘텐츠 제공업체에 대한 액세스를 제공하는 "올인원"이라는 서비스를 출시한다고 가정해 보겠습니다. 이제 OTT 플랫폼에 직접 가입해야 한다면 플랫폼별로 별도의 수수료를 지불해야 합니다. 우리는 모든 플랫폼을 몇 달 동안 구독할 필요가 없으므로 해당 서비스를 비용 효율적으로 사용할 수 있는 방법을 찾아야 합니다. start_month 배열에 지정된 i 플랫폼에 대한 서비스의 시작 월과 end_month 배열에 지정된 종료 월이 필요합니다. 플랫폼을 구독하는 데 필요한 가격은 배열 가격[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 USD만 지불하면 됩니다. 마찬가지로 두 번째 달에는 세 가지가 모두 필요하므로 총 비용은 $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

로그인 후 복사

Example

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. -

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

로그인 후 복사