自动搬运

查看原文

来自洛谷，原作者为

	Dregen_Yor 那时，我开始使用名叫数学的武器。但是，那种武器往往过于巨大，很多时候不能灵活操控。这种感觉正如我很难操控自己年轻时的青涩，很难控制对他们的思念一样。

搬运于2025-08-24 22:42:17，当前版本为作者最后更新于2022-11-21 21:07:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更好的阅读体验。

思路

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

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

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;
}