[JSOI2014]宅男计划

Description:

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

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

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

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

Hint:

对于100%的数据满足0<=Si<=10^{18,1<=F,Pi,M<=10}18,1<=N<=200

Solution:

很玄学的贪心+三分......
把题解的很多句话删掉了还是能过......

首先考虑送餐次数是个单峰的,三分即可,每次贪心时细节较多
详见代码:

// luogu-judger-enable-o2
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const ll mxn=1e6+5;
ll l,r,n,m,cnt,F,lmid,rmid,hd[mxn];

inline ll read() {
    char c=getchar(); ll x=0,f=1;
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
    return x*f;
}
inline void chkmax(ll &x,ll y) {if(xy) x=y;}

struct ed {
    ll to,nxt;
}t[mxn<<1];

inline void add(ll u,ll v) {
    t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt;
}

struct food {
    ll p,s;
    friend bool operator < (food x,food y) {
        if(x.p==y.p) return x.s>y.s; 
        return x.p=now&&w-a[i].p>=0) {
            p=min(a[i].s+1-now,w/a[i].p); //能买则买
            now+=p; w-=p*a[i].p;
        }
        s=i; /*记一个最多买到哪里,下面要用*/ if(w-a[i].p<0) break ;
    }
    k+=w*t; //剩下的钱
    for(ll i=s;i<=n;++i) {
        if(a[i].s>=now&&k-a[i].p>=0) {
            p=k/a[i].p; ans+=p;
            k-=p*a[i].p; //剩下来的钱也要用完
        }
    }
    return t*now+ans;
}

int main()
{
    m=read(); F=read(); n=read();
    for(ll i=1;i<=n;++i) a[i].p=read(),a[i].s=read();
    sort(a+1,a+n+1);  //贪心排序
    l=1;
    if(F!=0) r=m/F+1;
    else r=m+1;
    while(l=solve(rmid)) r=rmid-1;
        else l=lmid+1;
    }
    printf("%lld",max(solve(lmid),solve(rmid))); //取个max保险一些
    return 0;
}

三分贪心

[JSOI2014]宅男计划

Description:

Hint:

Solution:

相关

算法第四章《贪心策略》上机实践报告

洛谷 P2279 [HNOI2003]消防局的设立贪心

CF1479B Painting the Array（贪心+DP）

三分钟入门

cogs 1440. [NOIP2013]积木大赛贪心水题

天天快乐编程集训队2021暑假训练-0802-贪心题解

CF1190E Tokitsukaze and Explosion 二分、贪心、倍增、ST表

贪心学院计算机视觉CV训练营

海盗分金问题SQL求解（贪心算法）

贪心优化

51 Nod 1091 线段的重叠 (贪心算法)

贪心——55. 跳跃游戏 && 45.跳跃游戏II

标签