#2703. 能量之和
能量之和
【题目描述】
Alice搜集了一些三国卡片武将,每个卡片武将都有一个武力能量值。放学之后,Alice时不时拿出来给Bob看。
Bob最近迷上了数字之和的游戏。例如指定一个数值K,从一组固定的数中最多能选出多少个数,使得这些数的总和不超过K。 于是,Bob决定考考Alice,看Alice对自己的卡片武将能力是否滚瓜烂熟。
Bob向Alice询问m次,每次咨询一个数值K,而Alice需要回答最多可以使用多少张卡片,使得这些卡片的武力能量值之和不超过K。
Alice有点慌,他决定向你求助。
【输入格式】
输入第一行包含两个正整数n和m,n表示Alice的卡片武将数量,m表示Bob的咨询次数。 输入第二行包含n个正整数,表示每一个卡片武将的武力能量值。 输入第二行包含m个正整数,表示Bob每次咨询的数值K。
【输出格式】
输出一行m个整数,表示Bob每次咨询的数值K,相对应Alice的最多卡片数量。
【数据样例】
【输入数据 1】
4 3
4 5 2 1
3 10 21
【输出数据 1】
2 3 4
【输入数据 2】
4 1
2 3 4 5
1
【输出数据 2】
0
【说明/提示】
【样例 1 解释】
对于咨询数值3,【2,1】的和小于或等于3.可以证明满足题目要求的最多卡片个数是2,所以答案是2。
对于咨询数值10,【4,5,1】的和小于或等于10.可以证明满足题目要求的最多卡片个数是3,所以答案是3。
对于咨询数值21,【4,5,2,1】的和小于或等于21.可以证明满足题目要求的最多卡片个数是4,所以答案是4。
【样例 2 解释】
对于咨询数值1,只能选0个卡片,所以答案是0
【数据范围】
| 测试点编号 | n,m的范围 | k的范围 | 能量值范围 |
|---|---|---|---|
| 1~2 | 1≤n,m≤10 | 1≤k≤100 | ≤10 |
| 3~5 | 1≤n,m≤100 | 1≤k≤10000 | ≤100 |
| 6~10 | 1≤n,m≤1000 | 1≤k≤10^6 | ≤10^6 |
相关
在下列比赛中: