A15006 | Dolce Vita
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
Turbulent times are coming, so you decided to buy sugar in advance. There are $n$ shops around that sell sugar: the $i$ -th shop sells one pack of sugar for $a_i$ coins, but only one pack to one customer each day. So in order to buy several packs, you need to visit several shops.
Another problem is that prices are increasing each day: during the first day the cost is $a_i$ , during the second day cost is $a_i + 1$ , during the third day — $a_i + 2$ and so on for each shop $i$ .
On the contrary, your everyday budget is only $x$ coins. In other words, each day you go and buy as many packs as possible with total cost not exceeding $x$ . Note that if you don't spend some amount of coins during a day, you can't use these coins during the next days.
Eventually, the cost for each pack will exceed $x$ , and you won't be able to buy even a single pack. So, how many packs will you be able to buy till that moment in total?
Another problem is that prices are increasing each day: during the first day the cost is $a_i$ , during the second day cost is $a_i + 1$ , during the third day — $a_i + 2$ and so on for each shop $i$ .
On the contrary, your everyday budget is only $x$ coins. In other words, each day you go and buy as many packs as possible with total cost not exceeding $x$ . Note that if you don't spend some amount of coins during a day, you can't use these coins during the next days.
Eventually, the cost for each pack will exceed $x$ , and you won't be able to buy even a single pack. So, how many packs will you be able to buy till that moment in total?
输入格式
The first line contains a single integer $t$ ( $1 \le t \le 1000$ ) — the number of test cases. Next $t$ cases follow.
The first line of each test case contains two integers $n$ and $x$ ( $1 \le n \le 2 \cdot 10^5$ ; $1 \le x \le 10^9$ ) — the number of shops and your everyday budget.
The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^9$ ) — the initial cost of one pack in each shop.
It's guaranteed that the total sum of $n$ doesn't exceed $2 \cdot 10^5$ .
The first line of each test case contains two integers $n$ and $x$ ( $1 \le n \le 2 \cdot 10^5$ ; $1 \le x \le 10^9$ ) — the number of shops and your everyday budget.
The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^9$ ) — the initial cost of one pack in each shop.
It's guaranteed that the total sum of $n$ doesn't exceed $2 \cdot 10^5$ .
输出格式
For each test case, print one integer — the total number of packs you will be able to buy until prices exceed your everyday budget.
输入输出样例
输入 #1
4 3 7 2 1 2 5 9 10 20 30 40 50 1 1 1 2 1000 1 1
输出 #1
11 0 1 1500
In the first test case,
- Day 1: prices are $[2, 1, 2]$ . You can buy all $3$ packs, since $2 + 1 + 2 \le 7$ .
- Day 2: prices are $[3, 2, 3]$ . You can't buy all $3$ packs, since $3 + 2 + 3 > 7$ , so you buy only $2$ packs.
- Day 3: prices are $[4, 3, 4]$ . You can buy $2$ packs with prices $4$ and $3$ .
- Day 4: prices are $[5, 4, 5]$ . You can't buy $2$ packs anymore, so you buy only $1$ pack.
- Day 5: prices are $[6, 5, 6]$ . You can buy $1$ pack.
- Day 6: prices are $[7, 6, 7]$ . You can buy $1$ pack.
- Day 7: prices are $[8, 7, 8]$ . You still can buy $1$ pack of cost $7$ .
- Day 8: prices are $[9, 8, 9]$ . Prices are too high, so you can't buy anything.
In total, you bought $3 + 2 + 2 + 1 + 1 + 1 + 1 = 11$ packs.In the second test case, prices are too high even at the first day, so you can't buy anything.
In the third test case, you can buy only one pack at day one.
In the fourth test case, you can buy $2$ packs first $500$ days. At day $501$ prices are $[501, 501]$ , so you can buy only $1$ pack the next $500$ days. At day $1001$ prices are $[1001, 1001]$ so can't buy anymore. In total, you bought $500 \cdot 2 + 500 \cdot 1 = 1500$ packs.
- Day 1: prices are $[2, 1, 2]$ . You can buy all $3$ packs, since $2 + 1 + 2 \le 7$ .
- Day 2: prices are $[3, 2, 3]$ . You can't buy all $3$ packs, since $3 + 2 + 3 > 7$ , so you buy only $2$ packs.
- Day 3: prices are $[4, 3, 4]$ . You can buy $2$ packs with prices $4$ and $3$ .
- Day 4: prices are $[5, 4, 5]$ . You can't buy $2$ packs anymore, so you buy only $1$ pack.
- Day 5: prices are $[6, 5, 6]$ . You can buy $1$ pack.
- Day 6: prices are $[7, 6, 7]$ . You can buy $1$ pack.
- Day 7: prices are $[8, 7, 8]$ . You still can buy $1$ pack of cost $7$ .
- Day 8: prices are $[9, 8, 9]$ . Prices are too high, so you can't buy anything.
In total, you bought $3 + 2 + 2 + 1 + 1 + 1 + 1 = 11$ packs.In the second test case, prices are too high even at the first day, so you can't buy anything.
In the third test case, you can buy only one pack at day one.
In the fourth test case, you can buy $2$ packs first $500$ days. At day $501$ prices are $[501, 501]$ , so you can buy only $1$ pack the next $500$ days. At day $1001$ prices are $[1001, 1001]$ so can't buy anymore. In total, you bought $500 \cdot 2 + 500 \cdot 1 = 1500$ packs.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted