P4040 [AHOI2014/JSOI2014]宅男计划

    • 178通过
    • 688提交
  • 题目提供者 njH2Q
  • 评测方式 云端评测
  • 标签 贪心 各省省选 2014 安徽 江苏
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    自从迷上了拼图,JYY就变成了个彻底的宅男。为了解决温饱问题,JYY不得不依靠叫外卖来维持生计。

    题目描述

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

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

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

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

    输入输出格式

    输入格式:

    第一行包含三个整数M,F和N。

    接下来N行,第i行包含两个整数Pi和Si。

    输出格式:

    输出仅包含一行一个整数表示JYY可以宅的最多的天数。

    输入输出样例

    输入样例#1: 复制
    32 5 2
    5 0
    10 2
    输出样例#1: 复制
    3

    说明

    【样例说明】

    JYY的最佳策略是:

    第一天买一份食物1和一份食物2并且吃一份食物1;

    第二天吃一份食物2;

    第三天买一份食物1并且吃掉。

    【数据规模与约定】

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。