Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Chương trình C++ tìm chi phí thấp nhất đăng ký dịch vụ OTT

Mô tả bài toán

Có gói "all-in-one" giá k $/tháng cho n nền tảng. Đăng ký riêng nền tảng giá $/tháng, cần từ tháng đến . Tìm chi phí tối thiểu.

Ví dụ

n=3,k=10, start={1,2,1}, end={3,3,2}, price={5,7,8}. Đầu ra: 30 (mỗi tháng mua gói all-in-one 10$).

Thuật toán (Sweep line + Prefix)

  1. Tạo sự kiện: (start[i], +price[i]), (end[i]+1, -price[i]).
  2. Sắp xếp sự kiện theo tháng.
  3. Duyệt sự kiện: đoạn [pre, curMonth) có tổng giá riêng c, chi phí += min(k,c) * (curMonth-pre).
  4. Cập nhật c và pre.

Đoạn mã C++

#include <bits/stdc++.h>
using namespace std;

int solve(int n,int k,int start[],int end[],int price[]){
    vector<pair<int,int>> ev;
    for(int i=0;i

Đầu vào / Đầu ra

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

Output: 30