#PQJ324x6151. QOJ 324_6151

    ID: 2915 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:AHOI 2014堆贪心

QOJ 324_6151

2014 年安徽省青少年信息学奥林匹克竞赛

中学组试题 安徽 合肥 2014.4.18 宅男计划 【故事背景】 自从迷上了拼图,JYY 就变成了个彻底的宅男。为了解决温饱问题,JYY 不得不依靠叫外卖来维持生计。 【问题描述】 外卖店一共有N 种食物,分别有1 到N 编号。第i 种食物有固定的价钱 和 保质期 。第i 种食物会在 天后过期。JYY 是不会吃过期食物的。 比如JYY 如果今天点了一份保质期为1 天的食物,那么JYY 必须在今天或 者明天把这个食物吃掉,否则这个食物就再也不能吃了。保质期可以为0 天,这 样这份食物就必须在购买当天吃掉。 JYY 现在有M 块钱,每一次叫外卖需要额外付给送外卖小哥外送费F 元。 送外卖的小哥身强力壮,可以瞬间给JYY 带来任意多份食物。JYY 想知道,在 满足每天都能吃到至少一顿没过期的外卖的情况下,他可以最多宅多少天呢? 【输入格式】 从文件food.in 中读入数据。 第一行包含三个整数M,F 和N。 接下来N 行,第i 行包含两个整数 和 。 【输出格式】 输出到文件food.out 中。 输出仅包含一行一个整数表示JYY 可以宅的最多的天数。 【样例输入】 32 5 2 5 0 10 2 【样例输出】 3 【样例说明】 JYY 的最佳策略是: 第一天买一份食物1 和一份食物2 并且吃一份食物1;

2014 年安徽省青少年信息学奥林匹克竞赛

中学组试题 安徽 合肥 2014.4.18 第二天吃一份食物2; 第三天买一份食物1 并且吃掉。 【数据规模与约定】 对于10%的数据满足 ; 对于30%的数据满足 ; 对于60%的数据满足 ; 对于100%的数据满足 。