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

· · 题解

题目

这是一道贪心题,如果从第 1 天开始，每次选择单价最低那就错了。因为如果一种巧克力，它的单价最便宜，但是保质期最长，这个贪心就跳过另一个单价较低且保质期极短的商品，去选择单价最低的商品，但最优解得选保质期最短的。

既然正的做不行，就从反着来，从第 x 天开始。按保质期从长到短，将所有巧克力排序。选择保质期大于第 i 天，因为最优的巧克力已经在后面被用了，所以快到保质期的巧克力就会被选上。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    mutable int a,b,c;
    bool operator<(const node &t)const{
        if(a==t.a){
            return b>t.b;
        }
        return a>t.a;
    }
}w[100010];
bool cmp(node a,node b){
    return a.b<b.b;
}
int n,x,ans,maxn;
priority_queue<node> pq;
signed main(){
    cin>>x>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i].a>>w[i].b>>w[i].c;
        maxn=max(maxn,w[i].b);
    }
    if(maxn<x){
        puts("-1");
        return 0;
    }//如果保质期最大值小于天数直接输出-1
    sort(w+1,w+1+n,cmp);
    int top=n;
    for(int i=x;i;i--){
        while(w[top].b>=i){
            pq.push(w[top]);
            top--;
        }//保质期大于天数加入队列
        if(pq.empty()){
            puts("-1");
            return 0;
        }//如果已经没有巧克力直接输出-1
        ans+=pq.top().a;//钱
        pq.top().c--;//数量
        if(!q.top().c) pq.pop();//如果这种巧克力买完了就弹出队列
    }
    cout<<ans;
    return 0;
}