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$ 个查询的答案。

4 3
5 3 11 8
16
7
1000

3
1
4

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

1
1
2
2
2
3

2 2
1000000000 1000000000
200000000000000
1

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}$ 所有输入值均为整数。当有 $16$ 只驯鹿时，可以拉动雪橇 $1,2,4$。 用 $16$ 只驯鹿不可能拉动四辆雪橇，所以查询 $1$ 的答案是 $3$。

标签: AtCoder|abc334D

来源

AtCoder|abc334D