| 题目名称 | 2853. 邻值查找 |
|---|---|
| 输入输出 | dri.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 LGLJ
于2019-06-10加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：23， 提交：45， 通过率：51.11% | ||||
 Harry Potter |
100 | 0.105 s | 4.90 MiB | C++ |
 syzhaoss |
100 | 0.121 s | 2.12 MiB | C++ |
 增强型图元文件 |
100 | 0.192 s | 1.78 MiB | C++ |
|
锝镆氪锂铽 |
100 | 0.217 s | 4.28 MiB | C++ |
|
syzhaoss |
100 | 0.250 s | 4.29 MiB | C++ |
|
syzhaoss |
100 | 0.293 s | 4.27 MiB | C++ |
 数声风笛ovo |
100 | 0.311 s | 3.16 MiB | C++ |
|
yrtiop |
100 | 0.352 s | 2.05 MiB | C++ |
|
梦那边的美好ET |
100 | 0.448 s | 5.45 MiB | C++ |
 雾茗 |
100 | 0.457 s | 19.00 MiB | C++ |
| 关于 邻值查找 的近10条评论(全部评论) |
|---|
【题目描述】
给定一个长度为 $n$ 的序列 $A$，$A$ 中的数各不相同。对于 $A$ 中的每一个数 $A_i$，求：
$min（1 \le j<i）$ $\left|A_i-A_j\right|$
以及令上式取到最小值的 $j$（记为$ P_i$）。若最小值点不唯一，则选择使 $A_j$ 较小的那个。
【输入格式】
第一行一个整数n，第二行n个数$A_1···A_n$。
【输出格式】
n-1行，每行2个用空格隔开的整数。分别表示当$i$取$2···n$时，对应的$min（1 \le j<i）$ $\left|A_i-A_j\right|$和 $P_i$ 的值。
【样例输入】
3 1 5 3
【样例输出】
4 1 2 1
【提示】
对于30%的数据: n<=100
对于70%的数据: n<=10^4
对于100%的数据: n<=10^5, $|A_i|$<=10^9
【来源】
《算法竞赛进阶指南》