โปรแกรม C++ หาค่าใช้จ่ายน้อยที่สุดสำหรับการสมัครบริการ OTT

ผู้ให้บริโภคต้องการสมัครบริการ OTT n แพลตฟอร์ม มีแพ็กเกจ "all-in-one" ราคา k ดอลลาร์/เดือน (ดูทุกแพลตฟอร์ม) หรือสมัครแยกแต่ละตัว ราคา price[i] ต้องการแพลตฟอร์ม i ตั้งแต่เดือน start_month[i] ถึง end_month[i] หาค่าใช้จ่ายรวมน้อยที่สุด

ตัวอย่าง: n=3,k=10, start={1,2,1}, end={3,3,2}, price={5,7,8} ผลลัพธ์: 30 (จ่ายแพ็กเกจ 10 ต่อเดือน 3 เดือน = 30 ถูกกว่าสมัครแยก)

ขั้นตอนการแก้ปัญหา (Sweep Line / Event Sorting)

1. สร้างอาร์เรย์เหตุการณ์ pairArray:
   • (start_month[i], +price[i]) เริ่มต้องจ่าย
   • (end_month[i]+1, -price[i]) หยุดต้องจ่าย
2. เรียง pairArray ตามเดือน
3. Sweep: ตัวแปร c = ผลรวมราคาปัจจุบัน, pre = เดือนก่อนหน้า
   • สำหรับแต่ละ event (day, delta): เพิ่มค่าใช้จ่าย min(k, c) * (day - pre)
   • อัปเดต c += delta, pre = day
4. คืนผลรวม

ตัวอย่างโค้ด C++

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

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({start_month[i], price[i]});
        pairArray.push_back({end_month[i] + 1, -price[i]});
    }
    sort(pairArray.begin(), pairArray.end());
    int pre = 0, c = 0, 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;
    int start_month[] = {1, 2, 1};
    int end_month[] = {3, 3, 2};
    int 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