【贪心思想】巧克力

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
set<int>se;// 维护一个记录着没有安排巧克力吃的日期
struct node{
    int val , L , cnt;
    bool operator < (const node & b) const {
        if(val == b.val) return L > b.L;
        return val < b.val;
    }
}a[N];
signed main(){
    int x , n;
    cin >> x >> n;
    for(int i = 1 ; i <= n ; i ++){
        cin >> a[i].val >> a[i].L >> a[i].cnt;//val表示单价，L表示还剩几天，cnt表示数量
    }
    sort(a + 1 , a + 1 + n);//先将a其进行从小到大进行排序。
    for(int i = 1 ; i <= x ; i ++) se.insert(i);
    int p = 1 , res = 0;//p来代表是哪种巧克力，res来代表花费的总额
    while(se.size() && p <= n){
        while(a[p].cnt && se.size() && *se.begin() <= a[p].L){//在保质期前并且有这个巧克力
            res += a[p].val;//如果符合条件则加上这个巧克力的单价
            a[p].cnt --; //这个巧克力的数量减少一个
            auto it = se.upper_bound(a[p].L);
            it --;
            se.erase(it);
        }
        p ++ ;//进行下一种巧克力的选择
    }
    if(se.size()) cout << -1 << '\n';// 如果不存在让小蓝吃 x 天的购买方案
    else cout << res << '\n';// 输出一个整数表示小蓝的最小花费
    return 0;
}