← 返回题目列表

AtCoder · awc0107_c

C. 产品搜索系统

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥经营一家网上商店并负责 N 产品。产品编号为 1 to N和产品 i (1 \leq i \leq N) 的名称 S_i 和价格 V_i 日元。不同的产品可能具有相同的名称或相同的价格。

青木是这家店的顾客,已发送 Q 搜索请求。在 j第一个请求 (1 \leq j \leq Q),他指定一个整数 X_j 并询问:“请告诉我所有价格准确的产品 X_j 日元。”

然而,青木可能不记得确切的价格。因此,为了青木的方便,高桥决定按照以下规则返回搜索结果:

  • 如果存在一种或多种产品,其价格恰好为 X_j 日元,产量 全部 其名称位于一行,以空格分隔,按产品编号升序排列。即使多个匹配产品具有相同的名称,每个产品也会作为单独的产品输出一次(这意味着名称可能会在输出中出现重复)。
  • 如果没有产品的价格恰好为 X_j 日元,作为“您指的是该产品吗?”的建议,选择并输出价格最接近的一种产品 X_j。具体来说,候选者是使绝对差异最小化的产品 |V_i - X_j|。如果有多个候选产品(例如,一种产品同样便宜,另一种产品同样昂贵) X_j),选择其中产品编号最小的一个。输出 只有一个 单行中所选产品的名称。

确定每个请求的搜索结果。

约束

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • S_i 是长度介于 1 和 20 包含在内,仅由小写英文字母组成。
  • 1 \leq V_i \leq 10^9
  • 1 \leq X_j \leq 10^9
  • N, Q, V_i, X_j 均为整数。
  • 保证所有请求输出的产品名称总字符数(不包括分隔空格和换行符)不超过 10^6.

输入

N Q
S_1 V_1
S_2 V_2
\vdots
S_N V_N
X_1
X_2
\vdots
X_Q
  • 第一行包含产品数量 N 和搜索请求数 Q,用空格分隔。
  • 的 i- 以下各项 N 行 (1 \leq i \leq N) 包含字符串 S_i 代表产品名称 i 和整数 V_i 代表其价格,以空格分隔。
  • 的 j- 以下各项 Q 行包含价格 X_j 中指定 j第一个搜索请求。

输出

对于每个 Q 搜索请求,输出一行。

  • 如果存在一种或多种产品,其价格恰好为 X_j 日元,按产品编号升序输出其名称,以空格分隔。即使多个匹配产品具有相同的名称,也将每个产品输出为单独的产品。
  • 如果没有产品的价格恰好为 X_j 日元,仅输出最小化的产品中产品编号最小的产品名称 |V_i - X_j|.

示例输入 1

5 4
apple 100
banana 200
cherry 100
date 300
elderberry 500
100
250
300
150

示例输出 1

apple cherry
banana
date
apple

示例输入 2

4 5
milk 150
bread 150
cheese 300
butter 300
150
300
200
225
450

示例输出 2

milk bread
cheese butter
milk
milk
cheese

示例输入 3

10 8
notebook 1200
pen 300
eraser 100
ruler 500
pencil 300
marker 800
tape 250
glue 250
scissors 1500
stapler 1200
300
1200
100
700
2000
1
250
999

示例输出 3

pen pencil
notebook stapler
eraser
marker
scissors
eraser
tape glue
marker

示例输入 4

15 10
alpha 1000
beta 2000
gamma 3000
delta 4000
epsilon 5000
zeta 6000
eta 7000
theta 8000
iota 9000
kappa 10000
lambda 1000
mu 5000
nu 5000
xi 15000
omicron 20000
5000
1000
7500
1
1000000000
10000
15000
12000
20000
3500

示例输出 4

epsilon mu nu
alpha lambda
eta
alpha
omicron
kappa
xi
kappa
omicron
gamma

示例输入 5

1 1
a 1000000000
1000000000

示例输出 5

a