1.练习项目：

题目描述

小蓝很喜欢吃巧克力，他每天都要吃一块巧克力。

一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力，每种巧克力有自己的价格、数量和剩余的保质期天数，小蓝只吃没过保质期的巧克力，请问小蓝最少花多少钱能买到让自己吃 x 天的巧克力。

输入描述

输入的第一行包含两个整数 x,n，分别表示需要吃巧克力的天数和巧克力的种类数。

接下来 n 行描述货架上的巧克力，其中第 i 行包含三个整数 ai,bi,ci，表示第 i 种巧克力的单价为 ai​，保质期还剩 bi​ 天（从现在开始的 bi​ 天可以吃），数量为 ci​。

输出描述

输出一个整数表示小蓝的最小花费。如果不存在让小蓝吃 x 天的购买方案，输出 −1。

2.选择课程

在蓝桥云课中选择课程《16届蓝桥杯省赛无忧班（C&C++ 组）4期》，选择第二章“基础算法”编程37并开始练习。

3.开始练习

（1）源码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
//倒着分配。这样既能保证方案有效（保质期在），又能保证最优（最小）。
struct node{
    int a,b,c;    
    friend bool operator < (node x,node y){
        return x.a>y.a;
    }
}a[N];
bool comp(node x,node y){return x.b>y.b;}//按保质期从大到小排序
priority_queue<node>q;//按单价

int main()
{
    int t,n;cin>>t>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].a>>a[i].b>>a[i].c;
    }
    sort(a+1,a+n+1,comp);
    int j=1;
    long long ans=0;
    for(int i=t;i>=1;i--){
        while(j<=n&&a[j].b>=i){
            q.push(a[j]);
            j++;
        }
        if(q.empty()){
          cout<<-1;
          return 0;
        }
        node tmp=q.top();
        q.pop();
        ans+=tmp.a;
        tmp.c--;
        if(tmp.c>0){
            q.push(tmp);
        }
    }
    cout<<ans<<'\n';
    return 0;
}

（2）检验结果

对此代码进行检验，检验后无报错，提交此代码，判题结果为正确100分。

（3）练习心得：

为什么使用了两层循环但时间复杂度不是O(n*n)?

可以把内层 while 看作一个一次性扫描：它只是将所有符合条件的巧克力按顺序加入优先队列，每个巧克力只加入一次（初始入队）。后续天数中，队列中已经包含了所有可用的巧克力，只需从中选取即可。外层循环只是反复从队列中取元素，而不会再次触发扫描整个数组。

因此，虽然代码结构上有两层循环，但内层循环的总工作量与 n 成正比，与 t 无关，所以整体复杂度是线性的对数级别，而不是二次的。

注意每段代码末尾的分号是否存在，如不存在则需即使补充；输入法是否切换为英语模式；语法是否错误。