Description

外卖店一共有N种食物，分别有1到N编号。第i种食物有固定的价钱Pi和保质期Si。第i种食物会在Si天后过期。JYY是不会吃过期食物的。

比如JYY如果今天点了一份保质期为1天的食物，那么JYY必须在今天或者明天把这个食物吃掉，否则这个食物就再也不能吃了。保质期可以为0天，这样这份食物就必须在购买当天吃掉。

JYY现在有M块钱，每一次叫外卖需要额外付给送外卖小哥外送费F元。

送外卖的小哥身强力壮，可以瞬间给JYY带来任意多份食物。JYY想知道，在满足每天都能吃到至少一顿没过期的外卖的情况下，他可以最多宅多少天呢？

Solution

首先有个结论:答案与送外卖的次数所成的函数是单峰函数,可以三分

知道送外卖的次数之后,还有一个结论:一定每次购买的量尽量平均

也就是说对于任意一种物品在每一次购买的数量只差不超过 \(1\)

这样的话,我们就可以先把钱平均到每一次购买

然后发现我们可以把食物变成保质期随着价格递增的

这样的话排序之后贪心能买就买即可

#include
    
     using namespace std;template
     
      void gi(T &x){    int f;char c;    for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;    for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f;}typedef long long ll;const int N=205;int n;ll B,M;struct data{    ll w,t;    inline bool operator <(const data &p)const{        return w!=p.w?w
      
       p.t;    }}a[N];inline ll F(ll k){    ll s=M-k*B,e=s/k,r=s%k,t,ret=0;    if(s<=0)return 0;    int la=1;    for(int i=1;i<=n;i++){        if(a[i].t
       
        >M>>B>>n;  for(int i=1;i<=n;i++)gi(a[i].w),gi(a[i].t);  sort(a+1,a+n+1);  int cnt=0;a[0].t=-1;  for(int i=1;i<=n;i++)if(a[i].t>a[cnt].t)a[++cnt]=a[i];  n=cnt;  ll l=1,r=M/B+1,lm,rm,ans=0,vl,vr;  while(l<=r){      lm=l+(r-l)/3;rm=r-(r-l)/3;      if((vl=F(lm))>(vr=F(rm)))r=rm-1,ans=max(ans,vl);      else l=lm+1,ans=max(ans,vr);  }  cout<
        
         <