邻值查找

Luogu

IDLGP10466

Time1000ms

Memory512MB

DifficultyP3

链表

给定一个长度为 $n$ 的序列 $A$，$A$ 中的数各不相同。对于 $A$ 中的每一个数 $A_i$，求： $\min_{1 \le j <i}|A_i-A_j|$ 以及令上式取到最小值的 $j$（记为 $P_i$）。若最小值点不唯一，则选择使 $A_j$ 较小的那个。 ## Input 第一行输入整数 $n$，代表序列长度。第二行输入 $n$ 个整数 $A_1 \sim A_n$，代表序列的具体数值，数值之间用空格隔开。 ## Output 输出共 $n-1$ 行，每行输出两个整数，数值之间用空格隔开。分别表示当 $i$ 取 $2 \sim n$ 时，对应的 $\min_{1 \le j <i}|A_i-A_j|$ 和 $P_i$ 的值。 [samples] ## Note 对于 $30\%$ 的数据 $n \le 100$。对于 $70\%$ 的数据 $n \le 10^4$。对于 $100\%$ 的数据 $n \le 10^5,|A_i| \le 10^9$。

Samples

Input #1

3
1 5 3

Output #1

4 1
2 1

API Response (JSON)

{
  "problem": {
    "name": "邻值查找",
    "description": {
      "content": "给定一个长度为 $n$ 的序列 $A$，$A$ 中的数各不相同。 对于 $A$ 中的每一个数 $A_i$，求： $\\min_{1 \\le j <i}|A_i-A_j|$ 以及令上式取到最小值的 $j$（记为 $P_i$）。若最小值点不唯一，则选择使 $A_j$ 较小的那个。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10466"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个长度为 $n$ 的序列 $A$，$A$ 中的数各不相同。\n\n对于 $A$ 中的每一个数 $A_i$，求：\n\n$\\min_{1 \\le j <i}|A_i-A_j|$\n\n以及令上式取到最小值的 $j$（记为 $P_i$）。若最小值点不唯一，则选择使 $A_j$ 较小的那个。\n\n## Input\n\n第一行输入整数 $n$，代表序列长度。\n\n第二行输入 $n$ 个整数 $A_1 \\sim A_n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments