AT_abc334_d [ABC334D] Reindeer and Sleigh

题目描述

有 $N$ 台雪橇，每台雪橇编号为 $1,2,\ldots,N$。

拉动第 $i$ 台雪橇所需的驯鹿数量为 $R_i$。

此外，每只驯鹿最多只能拉一台雪橇。更严格地说，拉动 $m$ 台雪橇 $i_1,i_2,\ldots,i_m$ 所需的驯鹿总数为 $\sum_{k=1}^{m} R_{i_k}$。

现在给出 $Q$ 个如下形式的查询，请你回答每个查询：

• 给定整数 $X$，当有 $X$ 只驯鹿时，最多能拉动多少台雪橇？

输入格式

输入以如下格式从标准输入读入。

$N$ $Q$
$R_1$ $R_2$ $\ldots$ $R_N$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

每个查询为：

$X$

输出格式

输出 $Q$ 行。

第 $i$ 行输出第 $i$ 个查询的答案。

输入输出样例 #1

输入 #1

4 3
5 3 11 8
16
7
1000

输出 #1

3
1
4

输入输出样例 #2

输入 #2

6 6
1 2 3 4 5 6
1
2
3
4
5
6

输出 #2

1
1
2
2
2
3

输入输出样例 #3

输入 #3

2 2
1000000000 1000000000
200000000000000
1

输出 #3

2
0

说明/提示

限制

• $1 \leq N, Q \leq 2 \times 10^5$
• $1 \leq R_i \leq 10^9$
• $1 \leq X \leq 2 \times 10^{14}$
• 输入的所有数值均为整数

样例解释 1

当有 $16$ 只驯鹿时，可以拉动第 $1,2,4$ 号雪橇。用 $16$ 只驯鹿无法拉动 $4$ 台雪橇，因此第 $1$ 个查询的答案为 $3$。

由 ChatGPT 4.1 翻译