巧克力

題目描述

小藍(lán)很喜歡吃巧克力，他每天都要吃一塊巧克力。

一天小藍(lán)到超市想買一些巧克力。超市的貨架上有很多種巧克力，每種巧克力有自己的價(jià)格、數(shù)量和剩余的保質(zhì)期天數(shù)，小藍(lán)只吃沒過保質(zhì)期的巧克力，請問小藍(lán)最少花多少錢能買到讓自己吃 x 天的巧克力。

輸入描述

輸入的第一行包含兩個(gè)整數(shù) x, n，分別表示需要吃巧克力的天數(shù)和巧克力的種類數(shù)。

接下來 n 行描述貨架上的巧克力，其中第 i 行包含三個(gè)整數(shù) a_i, b_i, c_i，表示第 i 種巧克力的單價(jià)為 a_i，保質(zhì)期還剩 b_i 天（從現(xiàn)在開始的 b_i 天可以吃），數(shù)量為 c_i。

輸出描述

輸出一個(gè)整數(shù)表示小藍(lán)的最小花費(fèi)。如果不存在讓小藍(lán)吃 x 天的購買方案，輸出? -1。

輸入輸出樣例
示例

輸入

10 3
1 6 5
2 7 3
3 10 10

輸出

18

樣例說明
一種最佳的方案是第 1 種買 5 塊，第 2 種買 2 塊，第 3 種買 3 塊。前 5 天吃第 1 種，第 6、7 天吃第 2 種，第 8 至 10 天吃第 3 種。

評測用例規(guī)模與約定
對于 30% 的評測用例，n, x ≤ 1000。
對于所有評測用例，1 ≤ n, x ≤ 100000，1 ≤ a_i, b_i, c_i ≤ 10⁹。

解題分析

顯然要使花費(fèi)的錢最少，我們就要盡量選用價(jià)格盡量低的巧克力。

對于一個(gè)巧克力，設(shè)其保質(zhì)期為b，那么我們僅可能在第1~ b天會吃它。而如果第1~ b天每天都已經(jīng)安排好了要吃的巧克力，那該巧克力買了就沒有任何意義，我們稱其為沒用的巧克力。

假設(shè)我們現(xiàn)在買了一個(gè)保質(zhì)期為b的巧克力，那我們就要盡量將該巧克力放在第b天吃。而如果第b天已經(jīng)有巧克力吃了，我們就盡量將其放在b-1天吃

如此我們就能保證可以盡可能多的購買價(jià)格盡量低的有用的巧克力。

而對于保質(zhì)期為b的巧克力，要快速確定將其放在哪一天吃， 可以維護(hù)-一個(gè)記錄著沒有安排巧克力吃的日期的set，這樣我們只要在set中二分第一個(gè)小于b的日期就可以快速確定了。然后再通過以上貪心策略，模擬一遍即可。

或者利用隊(duì)列，從最后一天開始考慮，把符合要求的巧克力都加入備選集合，然后選擇價(jià)格最便宜的巧克力，用優(yōu)先隊(duì)列維護(hù)即可。

貪心

下面是對您提供的C++代碼的詳細(xì)注釋。

#include<bits/stdc++.h> // 引入所有標(biāo)準(zhǔn)庫
using namespace std;// 定義一個(gè)結(jié)構(gòu)體node，用來表示巧克力的屬性
struct node
{int val,days,cnt; // val: 單價(jià), days: 保質(zhì)期剩余天數(shù), cnt: 數(shù)量
}p[100010]; // 創(chuàng)建一個(gè)node數(shù)組p，用來存儲每種巧克力的信息// 自定義比較函數(shù)cmp，用于排序
bool cmp(node a, node b)
{// 如果價(jià)格相同，則按照保質(zhì)期剩余天數(shù)從大到小排序if(a.val == b.val) return a.days > b.days;// 否則按照價(jià)格從小到大排序return a.val < b.val;
}// 定義一個(gè)集合day，用來存儲x天，即小藍(lán)吃巧克力的每一天
set<int> day;int main()
{int x, n; // x: 需要吃巧克力的天數(shù), n: 巧克力的種類數(shù)cin >> x >> n; // 讀入x和n的值// 循環(huán)讀入每種巧克力的價(jià)格、保質(zhì)期剩余天數(shù)和數(shù)量for(int i = 1; i <= n; i++)cin >> p[i].val >> p[i].days >> p[i].cnt;// 根據(jù)自定義的比較函數(shù)cmp對巧克力數(shù)組p進(jìn)行排序sort(p + 1, p + n + 1, cmp);// 初始化集合day，存入每一天作為元素for(int i = 1; i <= x; i++)day.insert(i);long long sum = 0; // sum用來記錄總花費(fèi)int q = 1; // q用來遍歷每一種巧克力// 當(dāng)仍有需要吃的天數(shù)且還有巧克力未考慮時(shí)，執(zhí)行循環(huán)while(day.size() != 0 && q <= n){// 當(dāng)當(dāng)前巧克力還有剩余、還有需要吃的天數(shù)、// 并且最早的未安排的天數(shù)小于等于當(dāng)前巧克力的保質(zhì)期時(shí)，執(zhí)行循環(huán)while(p[q].cnt != 0 && day.size() != 0 && *day.begin() <= p[q].days){sum += p[q].val; // 累加當(dāng)前巧克力的價(jià)格到總花費(fèi)p[q].cnt--; // 當(dāng)前巧克力的數(shù)量減一// 使用upper_bound找到第一個(gè)大于當(dāng)前巧克力保質(zhì)期的天數(shù)，然后往前移動一個(gè)位置auto t = day.upper_bound(p[q].days);t--;// 從集合day中刪除已經(jīng)安排給當(dāng)前巧克力的天數(shù)day.erase(t);}q++; // 考慮下一種巧克力}// 如果day集合不為空，說明存在無法滿足吃完x天的巧克力的情況，輸出-1if(day.size() != 0) cout << "-1";// 否則輸出總花費(fèi)sumelse cout << sum;return 0;
}

代碼的工作流程如下：

1. 讀入需要吃巧克力的天數(shù)x和巧克力的種類數(shù)n。
2. 讀入每種巧克力的價(jià)格、保質(zhì)期剩余天數(shù)和數(shù)量，存入數(shù)組p。
3. 根據(jù)價(jià)格和保質(zhì)期對巧克力進(jìn)行排序。
4. 初始化一個(gè)集合day，表示小藍(lán)每天都需要吃巧克力。
5. 遍歷每種巧克力，同時(shí)檢查集合day中是否有對應(yīng)的天需要吃巧克力。
6. 如果找到匹配的天數(shù)，就從day中移除該天，并從當(dāng)前種類的巧克力數(shù)量中減去一塊，同時(shí)累加其價(jià)格到總花費(fèi)sum中。
7. 最后，如果day集合為空，表明所有天都分配了巧克力，輸出總花費(fèi)；如果day不為空，輸出-1，表示無法滿足小藍(lán)全部天數(shù)的巧克力需求。