本文共 1311 字，大约阅读时间需要 4 分钟。

【题目】

【题解】

这道题的主要问题在于，题干比较难读hhh

题意：饭店有n种菜，编号为i∈[1,n]的菜的初始量为ai，价格为bi。有m个客人，每个客人会点d盘编号为t的菜。假设此时的菜的余量为ri，如果ri充足，那么给客人上d盘编号为t的菜，正常消费；如果ri不足，那么剩下的盘数将由剩余最便宜的菜代替，如果价格一样低，编号小的优先被代替；如果ri不足并且没有足够的其他的菜，那么客人会生气的走掉，消费为0并且会拿走之前消费的菜。

思路：能上t就上t，不能上t就最便宜，按菜品消费。如果剩下所有盘数都不足d，那么客人肯定会生气的走掉，并且之后的客人都会生气因为余量为0。问题在于，寻找最便宜需要排序，但是客人直接点编号为t的菜时又不能被排序不然不能直接减掉被消费的菜和计算消费价格。思考了一下，我们只需要按价格和序号对序号排个序即可，然后定义pos存储当前最小的菜品的编号，每次分类讨论即可。

还有一点，第一发wa了，然后改成long long才过的。

我可真是个小机灵鬼儿~  

【代码】

#include
   
    using namespace std;typedef long long ll;struct p{    ll num;    ll cc;}f[100005];bool cmp(p x,p y){    if(x.cc==y.cc) return x.num
    
     =d) sum-=d;        else        {            puts("0");            sum=0;            continue;        }        ll ans=0;        if(a[t]>=d) ans=d*c[t],a[t]-=d;        else        {            d-=a[t];            ans+=a[t]*c[t],a[t]=0;            while(d)            {                while(a[f[pos].num]==0) pos++;                ll poss=f[pos].num;                if(a[poss]>=d)                {                    a[poss]-=d,ans+=d*c[poss];                    d=0;                }                else                {                    ans+=a[poss]*c[poss];                    d-=a[poss];                    a[poss]=0;                }            }        }        printf("%I64d\n",ans);    }    return 0;}
    
   

转载地址：http://sfben.baihongyu.com/