description

外卖店一共有N种食物，分别有1到N编号。第i种食物有固定的价钱Pi和保质期Si。第i种食物会在Si天后过期。JYY是不会吃过期食物的。
比如JYY如果今天点了一份保质期为1天的食物，那么JYY必须在今天或
者明天把这个食物吃掉，否则这个食物就再也不能吃了。保质期可以为0天，这
样这份食物就必须在购买当天吃掉。
JYY现在有M块钱，每一次叫外卖需要额外付给送外卖小哥外送费F元。
送外卖的小哥身强力壮，可以瞬间给JYY带来任意多份食物。JYY想知道，在
满足每天都能吃到至少一顿没过期的外卖的情况下，他可以最多宅多少天呢？

analysis

• 首先除掉垃圾食品，即价钱比其他的高、保质期还短的，肯定不买；剩下来的价钱和保质期都单调递增，价钱越高保质期一定越长

• 考虑送外卖的人来的次数对答案的影响，容易知道次数太多或太少都不优，外卖费或食物贵，而实际上答案与次数成单峰函数的关系

• 三分送外卖的人来的次数\(x\)，再判定来\(x\)次的最长续命；每一次送餐，都贪心地平均分配钱，然后只考虑一次送餐的答案再乘\(x\)

• 对于只一开始买食物中途吃，其实都是买保质期最短的食物若干份，保质期不够的，再买保质期第二短的若干份，如此下去

• 这个当然\(O(n)\)很好做；剩下还有一点钱，则贪心考虑拼到其中一次买餐的后面多续几天；总的来说两个贪心一个三分

code

#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 205
#define ll long long
#define reg register ll
#define fo(i,a,b) for (reg i=a;i<=b;++i)
#define fd(i,a,b) for (reg i=a;i>=b;--i)

using namespace std;

ll n,fee,tot,money;
bool bz[MAXN];

struct node
{
    ll x,y,id;
}a[MAXN],b[MAXN];

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline bool cmp(node a,node b){return a.x<b.x;}
inline ll check(ll x)
{
    ll rest=money-x*fee,ave=rest/x,left=rest-ave*x,rec,day=0,ans=0;
    fo(i,1,n)
    {
        if (a[i].y>=day && a[i].x<=ave)
        {
            ll tmp=min(a[i].y-day+1,ave/a[i].x);
            ave-=a[i].x*tmp,day+=tmp;
        }
        rec=i;
        if (a[i].x>ave)break;
    }
    left+=ave*x;
    fo(i,rec,n)
    {
        if (a[i].y>=day && a[i].x<=left)
        {
            ll tmp=left/a[i].x;
            left-=tmp*a[i].x,ans+=tmp;
        }
        if (ans)break;
    }
    return day*x+ans;
}
int main()
{
    freopen("food.in","r",stdin);
    freopen("food.out","w",stdout);

    money=read(),fee=read(),n=read();
    fo(i,1,n)a[i].x=read(),a[i].y=read(),a[i].id=i;
    memset(bz,1,sizeof(bz));
    fo(i,1,n)fo(j,1,n)if (i!=j && a[j].x<=a[i].x && a[j].y>=a[i].y){bz[i]=0;break;}

    fo(i,1,n)if (bz[i])b[++tot]=a[i];n=tot;
    sort(b+1,b+n+1,cmp);fo(i,1,n)a[i]=b[i];

    ll l=1,r=fee?money/fee:money+1,midl,midr;
    while (l<r)midl=l+(r-l)/3,midr=r-(r-l)/3,check(midl)>=check(midr)?r=midr-1:l=midl+1;
    printf("%lld\n",check(l));
    return 0;
}

【JZOJ3673】【luoguP4040】【BZOJ3874】宅男计划

原文：https://www.cnblogs.com/horizonwd/p/12040777.html