题目详情题解（0）讨论（0）提交记录（0）

AT_abc283_f.[ABC283F] Permutation Distance

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个 $ (1,2,\ldots,N) $ 的排列 $ P=(P_1,P_2,\ldots,P_N) $。

对于所有 $ i\ (1\leq i\leq N) $，请计算以下的值：

  • $ D_i = \displaystyle\min_{j\neq i}\left( |P_i - P_j| + |i - j| \right) $

排列是指将 $ (1,2,\ldots,N) $ 重新排列得到的数列。也就是说，长度为 $ N $ 的数列 $ A $，当且仅当 $ i\ (1\leq i\leq N) $ 在其中恰好出现一次时，$ A $ 是 $ (1,2,\ldots,N) $ 的一个排列。

输入格式

输入以以下格式从标准输入读入。

$ N\ P_1\ P_2\ \ldots\ P_N $

输出格式

请按 $ i $ 的升序，用空格分隔输出 $ D_i\ (1\leq i\leq N) $。

输入输出样例

  • 输入#1

    4
3 2 4 1

    输出#1

    2 2 3 3

  • 输入#2

    7
1 2 3 4 5 6 7

    输出#2

    2 2 2 2 2 2 2

  • 输入#3

    16
12 10 7 14 8 3 11 13 2 5 6 16 4 1 15 9

    输出#3

    3 3 3 5 3 4 3 3 4 2 2 4 4 4 4 7

说明/提示

限制条件

  • $ 2 \leq N \leq 2\times 10^5 $
  • $ 1 \leq P_i \leq N\ (1\leq i\leq N) $
  • $ i\neq j \implies P_i\neq P_j $
  • 输入均为整数

样例解释 1

例如，对于 $ i=1 $：

  • 当 $ j=2 $ 时，$ |P_i - P_j|=1,\ |i-j|=1 $。
  • 当 $ j=3 $ 时，$ |P_i - P_j|=1,\ |i-j|=2 $。
  • 当 $ j=4 $ 时，$ |P_i - P_j|=2,\ |i-j|=3 $。

因此，当 $ j=2 $ 时 $ |P_i - P_j|+|i-j|=2 $，为最小值，所以 $ D_1=2 $。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页