AT_abc268_e [ABC268E] Chinese Restaurant (Three-Star Version)

题目描述

在转盘桌的周围，按照逆时针方向等间隔地排列着人 $0$、人 $1$、$\ldots$、人 $N-1$。此外，在人 $i$ 的正前方放着菜品 $p_i$。

你可以进行如下操作任意多次（包括 $0$ 次）：

• 将转盘桌逆时针旋转 $\frac{1}{N}$ 圈。这样一来，（在这次操作之前）人 $i$ 正前方的菜品会移动到人 $(i+1)\bmod N$ 的正前方。

在操作完成后，对于每个人 $i$，其不满度定义为：使得菜品 $i$ 被放在了人 $(i-k)\bmod N$ 或 $(i+k)\bmod N$ 的正前方的最小非负整数 $k$。

请你求出 $N$ 个人的不满度总和的最小值。

$a\bmod m$ 表示对于整数 $a$ 和正整数 $m$，$a\bmod m$ 是满足 $a-x$ 为 $m$ 的倍数的 $0$ 以上小于 $m$ 的整数 $x$。（可以证明，这样的 $x$ 是唯一确定的。）

输入格式

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

$N$ $p_0$ $p_1$ $\ldots$ $p_{N-1}$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4
1 2 0 3

输出 #1

2

输入输出样例 #2

输入 #2

3
0 1 2

输出 #2

0

输入输出样例 #3

输入 #3

10
3 9 6 1 7 2 8 0 5 4

输出 #3

20

说明/提示

限制条件

• $3 \leq N \leq 2 \times 10^5$
• $0 \leq p_i \leq N-1$
• 若 $i \neq j$，则 $p_i \neq p_j$
• 输入均为整数

样例解释 1

若进行 $1$ 次操作，情况如下图所示。

此时，不满度总和为 $2$，具体如下：

• 人 $0$ 的不满度为 $1$，因为菜品 $0$ 被放在了人 $3\ (=(0-1)\bmod 4)$ 的正前方。
• 人 $1$ 的不满度为 $0$，因为菜品 $1$ 被放在了人 $1\ (=(1+0)\bmod 4)$ 的正前方。
• 人 $2$ 的不满度为 $0$，因为菜品 $2$ 被放在了人 $2\ (=(2+0)\bmod 4)$ 的正前方。
• 人 $3$ 的不满度为 $1$，因为菜品 $3$ 被放在了人 $0\ (=(3+1)\bmod 4)$ 的正前方。

无法使不满度总和小于 $2$，因此答案为 $2$。

由 ChatGPT 4.1 翻译