P8769 [蓝桥杯 2021 国 C] 巧克力 题解

· · 题解

更好的阅读体验。

思路

为了尽可能地减小吃巧克力的花费，我们考虑用一个堆来维护当前没有过期的巧克力中的最小值，我们考虑从最后一天开始向前枚举，并将当天没有过期的巧克力加入堆中，每天取堆的最小值，并判断数量是否耗尽即可。

但如果是从第一天开始遍历的话，这样算出来的答案是不对的，我们举一个样例：

5 3
1 4 3
2 1 1
10 5 5
15

但如果从第一天开始遍历，结果是 23。

最优解应该是第一天时选择第 2 种，第二，三，四天选择第 1 种，第五天选择第 3 种。

但如果从第一天开始遍历，就会跳过第二种巧克力，只选择第三种和第二种。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    mutable int a,b,c;
    bool operator<(const node &B)const{
        if(a==B.a){
            return b>B.b;
        }
        return a>B.a;
    }
}w[100010];
bool cmp(node a,node b){
    return a.b<b.b;
}
int n,x,ans,maxn;
signed main(){
    scanf("%lld%lld",&x,&n);
    priority_queue<node> q;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld%lld",&w[i].a,&w[i].b,&w[i].c);
        maxn=max(maxn,w[i].b);
        //q.push(w[i]);
    }
    // if(maxn<x){
    //     puts("-1");
    //     return 0;
    // }
    sort(w+1,w+1+n,cmp);
    int top=n;
    for(int i=x;i;i--){
        while(w[top].b>=i){
            q.push(w[top]);
            --top;
        }
        // if(q.empty()){
        //     puts("-1");
        //     return 0;
        // }
        ans+=q.top().a;
        q.top().c--;
        if(!q.top().c){
            q.pop();
        }
    }
    printf("%lld",ans);
    return 0;
}