A104882.星港补给舱调度
普及-
官方
通过率:0%
时间限制:3.00s
内存限制:256MB
题目描述
在遥远的星港“冬至号”空间站,今晚要进行一场紧急补给投送行动。空间站里停靠着 N 个补给舱,编号为 1,2,…,N。
- 第 i 个补给舱想要被成功推出并进入预定航道,需要消耗 Ri 单位的推进燃料。
- 每 1 单位燃料最多只能用于一个补给舱,不能重复使用。
- 只要燃料足够,可以选择任意数量任意编号的补给舱推出。
如果要同时推出 m 个补给舱 i1,i2,…,im,则至少需要燃料总量
k=1∑mRik
个单位,即各个推出补给舱所需的燃料之和。
由于太空中情况多变,现在空间站会收到 Q 个询问:
给定一个整数 X,表示当前可用燃料为 X 单位,指挥官想知道最多能推出多少个补给舱?
输入格式
第一行输入两个整数 N,Q,分别表示补给舱数量和询问次数。
第二行输入 N 个整数表示每个补给舱所需的燃料 Ri。
接下来 Q 行,每行输入一个整数 X 表示可用燃料数量。
输出格式
输出 Q 行。第 i 行输出第 i 次询问的答案。
输入输出样例
输入#1
2 2 1000000000 1000000000 200000000000000 1
输出#1
2 0
输入#2
4 3 5 3 11 8 16 7 1000
输出#2
3 1 4
说明/提示
1≤N,Q≤2×105
1≤Ri≤109
1≤X≤2×1014