A6488 | [NOIP2025] 糖果店
来源NOIP提高组 / 2025
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
NOIP2025 T1
小 X 开了一家糖果店,售卖 $n$ 种糖果,每种糖果均有无限颗。对于不同种类的糖果,小 X 采用了不同的促销策略。具体地,对于第 $i$ ($1 \le i \le n$) 种糖果,购买第一颗的价格为 $x_i$ 元,第二颗为 $y_i$ 元,第三颗又变回 $x_i$ 元,第四颗则为 $y_i$ 元,以此类推。
小 R 带了 $m$ 元钱买糖果。小 R 不关心糖果的种类,只想到得到数量尽可能多的糖果。你需要帮助小 R 求出,$m$ 元钱能购买的糖果数量的最大值。
小 X 开了一家糖果店,售卖 $n$ 种糖果,每种糖果均有无限颗。对于不同种类的糖果,小 X 采用了不同的促销策略。具体地,对于第 $i$ ($1 \le i \le n$) 种糖果,购买第一颗的价格为 $x_i$ 元,第二颗为 $y_i$ 元,第三颗又变回 $x_i$ 元,第四颗则为 $y_i$ 元,以此类推。
小 R 带了 $m$ 元钱买糖果。小 R 不关心糖果的种类,只想到得到数量尽可能多的糖果。你需要帮助小 R 求出,$m$ 元钱能购买的糖果数量的最大值。
输入格式
输入的第一行包含两个正整数 $n, m$,代表糖果的种类数和小 R 的钱数。
输入的第 $i+1$ ($1 \le i \le n$) 行包含两个正整数 $x_i, y_i$,分别表示购买第 $i$ 种糖果时第奇数颗的价格和第偶数颗的价格。
输入的第 $i+1$ ($1 \le i \le n$) 行包含两个正整数 $x_i, y_i$,分别表示购买第 $i$ 种糖果时第奇数颗的价格和第偶数颗的价格。
输出格式
输出一行一个非负整数,表示 $m$ 元钱能购买的糖果数量的最大值。
输入输出样例
输入 #1
2 10 4 1 3 3
输出 #1
4
### 【样例 1 解释】
小 R 可以购买 4 颗第一种糖果,共花费 $4 + 1 + 4 + 1 = 10$ 元。
### 【数据范围】
对于所有测试数据,均有:
- $1 \le n \le 10^5$;
- $1 \le m \le 10^{18}$;
- 对于所有 $1 \le i \le n$,均有 $1 \le x_i, y_i \le 10^9$。
| 测试点编号 | $n \le$ | $m \le$ | 特殊性质 |
|:----------:|:--------:|:--------:|:--------:|
| 1 | 1 | 10 | 无 |
| 2,3 | 2 | 20 | 无 |
| 4,5 | 10 | 20 | 无 |
| 6 | $10^2$ | $10^2$ | A |
| 7 | $10^2$ | $10^2$ | B |
| 8,9 | $10^2$ | $10^2$ | 无 |
| 10 | $10^3$ | $10^4$ | A |
| 11,12 | $10^3$ | $10^4$ | B |
| 13 | $10^3$ | $10^4$ | 无 |
| 14 | $10^5$ | $10^9$ | A |
| 15,16 | $10^5$ | $10^9$ | B |
| 17,18 | $10^5$ | $10^9$ | 无 |
| 19,20 | $10^5$ | $10^{18}$ | 无 |
特殊性质 A:对于所有 $1 \le i \le n$,均有 $x_i = y_i$。
特殊性质 B:对于所有 $1 \le i \le n$,均有 $x_i \ge y_i$。
小 R 可以购买 4 颗第一种糖果,共花费 $4 + 1 + 4 + 1 = 10$ 元。
### 【数据范围】
对于所有测试数据,均有:
- $1 \le n \le 10^5$;
- $1 \le m \le 10^{18}$;
- 对于所有 $1 \le i \le n$,均有 $1 \le x_i, y_i \le 10^9$。
| 测试点编号 | $n \le$ | $m \le$ | 特殊性质 |
|:----------:|:--------:|:--------:|:--------:|
| 1 | 1 | 10 | 无 |
| 2,3 | 2 | 20 | 无 |
| 4,5 | 10 | 20 | 无 |
| 6 | $10^2$ | $10^2$ | A |
| 7 | $10^2$ | $10^2$ | B |
| 8,9 | $10^2$ | $10^2$ | 无 |
| 10 | $10^3$ | $10^4$ | A |
| 11,12 | $10^3$ | $10^4$ | B |
| 13 | $10^3$ | $10^4$ | 无 |
| 14 | $10^5$ | $10^9$ | A |
| 15,16 | $10^5$ | $10^9$ | B |
| 17,18 | $10^5$ | $10^9$ | 无 |
| 19,20 | $10^5$ | $10^{18}$ | 无 |
特殊性质 A:对于所有 $1 \le i \le n$,均有 $x_i = y_i$。
特殊性质 B:对于所有 $1 \le i \le n$,均有 $x_i \ge y_i$。
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?