蓝桥杯 巧克力

首先这是一道贪心思想的题目，贪心思想我觉得是考（思维+模拟）的题目。

正文：依据题目要求总价最少，那么我们就从价格低的巧克力开始选择。每一天放置一块巧克力。假如当前巧克力k1单价最便宜，保质期为k1.date，那么尽量把当前巧克力放置在第k1.date天的位置上，把前面的位置留出来给保质期短一些的巧克力(保质期短的当然无法放置在k1.date或者说大于其保质期的位置上)，如果你占用了比你保质期短的巧克力位置，那么就会造成总价提升。如果k1.date的位置上有了巧克力了那就往前去找呗(往后找你也没有那么长保质期啊) 

#include<bits/stdc++.h>
#define get getchar
#define put putchar
#define il inline
#define is isdigit
#define dfor(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
typedef long long ll;
const int N=1e5+1;
int n,x;
ll ans;//这道题极限数据单价是10的九次方，谁知道会不会爆int，保险起见用long long
set<int>s;
struct p 
{
    int val,date,cnt;
    il bool operator<(const p&b) const    //重载运算符没学过的同学下面会有函数判断的代码
    {
        if(val==b.val) return date>b.date;
        return val<b.val;
    }
    p(){}
    p(int aa,int bb,int cc)
    {
        val=aa,date=bb,cnt=cc;
    }
}node[N];
int read(void)//快读不会的同学可以不管下面会有没有快读快写的代码
{
    int x=0,f=1;
    char c=get();
    while(!is(c))
    {
        if(c=='-') f=-1;
        c=get();
    }
    while(is(c)) x=(x<<1)+(x<<3)+(c^48),c=get();
    return x*f;
}
void write(ll x)//快写
{
    if(x>9) write(x/10);
    put((x%10)^48);
}
int main()
{
    x=read(),n=read();
    int a,b,c;
    dfor(i,1,n) a=read(),b=read(),c=read(),node[i]=p(a,b,c);
    sort(node+1,node+n+1);
    int now=1;
    dfor(i,1,x) s.insert(i);    //用set去维护没有被放置巧克力的某一天，先把每一天都放进去，当某一天放置了巧克力就删去这一天
    while(s.size()&&now<=n)    //要是s.size()为0了那不每一天都有巧克力了吗，要是now都等于n了所有巧克力都被遍历了一定会有一个结果
    {   
        while(node[now].cnt&&s.size()&&node[now].date>=*s.begin())//cnt为0的话该巧克力被炫光了，s.size()同理，set自身是升序排列，当前巧克力的保质期不能小于现有的最小天数(会过期啊)
        {
            ans+=node[now].val,--node[now].cnt;//选一块巧克力就加上其价格，数量减一
            auto i=s.upper_bound(node[now].date);//upper_bound找出大于目标的第一个数，找不到就返回对应的end，为什么不用lower_bound(找出大于等于目标的第一个数..)，因为你选择的保质期有可能是放置在小于你保质期前面的
            --i,s.erase(i);//--找到你应该放置的位置，删去这个位置
        }
        ++now;//下一个种类
    }
    if(s.size()) puts("-1");
    else write(ans);
    return 0;
}

#include<bits/stdc++.h>
#define get getchar
#define put putchar
#define il inline
#define is isdigit
#define dfor(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
typedef long long ll;
const int N=1e5+1;
int n,x;
ll ans;
set<int>s;
struct p 
{
    int val,date,cnt;
    p(){}
    p(int aa,int bb,int cc)
    {
        val=aa,date=bb,cnt=cc;
    }
}node[N];
bool cmp(p a,p b)
{
  if(a.val==b.val) return a.date>b.date; //单价一样肯定选择保质期长的啊
  return a.val<b.val;//单价低在前面先选
}
int main()
{
    cin>>x>>n;
    int a,b,c;
    for(int i=1;i<=n;++i) cin>>a>>b>>c,node[i]=p(a,b,c);
    sort(node+1,node+n+1,cmp);
    int now=1;
    for(int i=1;i<=x;++i) s.insert(i);
    while(s.size()&&now<=n)
    {   
        while(node[now].cnt&&s.size()&&node[now].date>=*s.begin())
        {
            ans+=node[now].val,--node[now].cnt;
            auto i=s.upper_bound(node[now].date);
            --i,s.erase(i);
        }
        ++now;
    }
    if(s.size()) puts("-1");
    else cout<<ans;
    return 0;
}