AlgoMooc
你已开通华为OD训练营权益,还差最后一步——完成入营激活(兑换课程 + 加飞书 + 登记服务群),即可解锁全部课程与专属服务。去激活 →
← 返回题库

K0075. 魔法水晶的匹配仪式

中等通过率 55% · 提交 58 · 通过 32
模拟排序哈希表贪心

在“小慕的魔法水晶”项目中,小慕拥有一批编号从 0 开始的魔法水晶,每颗水晶都有固定的魔力值。每当月圆之夜,小慕会收到一批魔法卷轴,每张卷轴都需要足够的魔力值才能成功激活。 为了合理分配魔力资源,每颗水晶在一轮仪式中只能使用一次。 在激活仪式中,每张卷轴将依次寻找一颗尚未被使用且满足条件的水晶来启动: * 只能选择一颗的水晶(即 `水晶 >= 卷轴`); * 若有多颗水晶满足条件,; * 若魔力值相同,选择的水晶(编号从 `0` 开始); * 若没有任何水晶满足条件,则此次激活失败,返回 `-1`; * 每颗水晶只能匹配成功一次,成功匹配后将无法再次用于其他卷轴。

提示:带虚线的词点一下有通俗解释。

输入描述

第一行输入一个整数 `n`,表示魔法水晶的数量。 第二行输入 `n` 个整数,表示每颗水晶的魔力值(单位:魔力点),中间用空格隔开。 第三行输入一个整数 `m`,表示待激活的魔法卷轴数量。 第四行输入 `m` 个整数,表示每张卷轴所需的魔力值(单位:魔力点),中间用空格隔开。 * `1 <= n, m <= 200000` * `1 <= 魔力值 <= 10^9`

输出描述

输出一行 `m` 个整数,依次表示每张卷轴所匹配的水晶编号,若无法匹配则输出 `-1`。编号之间用空格分隔。

示例

示例 1

输入

4
128 256 64 196
4
128 64 64 512

输出

0 2 3 -1

说明:* 第 1 张卷轴需 128 魔力,水晶 0(128)刚好满足,选编号最小的 0; * 第 2 张卷轴需 64 魔力,水晶 2(64)满足,选 2; * 第 3 张卷轴需 64 魔力,水晶 2 已用,水晶 3(196)满足,选 3; * 第 4 张卷轴需 512 魔力,所有剩余水晶都不足,输出 -1。

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解
魔法水晶匹配流程(示例) 水晶0 128 水晶1 256 水晶2 64 水晶3 196 卷轴1 需128 卷轴2 需64 卷轴3 需64 卷轴4 需512 → 匹配水晶0 → 匹配水晶2 → 匹配水晶3 → 无匹配 -1 (已用) (已用) (已用)
写完代码点「提交」,将对全部测试用例判题。

向老师提问

针对「魔法水晶的匹配仪式」把疑问、代码和报错填清楚,老师收到后能更快、更准地回复你。