P11652 [COCI 2024/2025 #4] 鞋 / Cipele（疑似错题）

题目背景

译自 COCI 2024/2025 #4 T4。$\texttt{2s,0.5G}$。满分为 $120$。

根据讨论，本题为错题，可能不存在靠谱做法。

题目描述

有 $n$ 双鞋，标号 $1\sim n$。鞋柜是一个栈，初始鞋都在鞋柜中，从栈顶到栈底依次是第 $1,2,\ldots,n$ 双鞋。

接下来 $q$ 天，第 $i$ 天要穿标号为 $a_i$ 的鞋。如果这双鞋是栈顶到栈底第 $j$ 双鞋，则需要 $j$ 秒将其拿出（不改变其他鞋的相对顺序）；如果这双鞋在走廊里，则不花费时间。

每天结束时，可以选择将标号为 $a_i$ 的鞋入栈，或者放在走廊里。走廊里至多能放 $m$ 双鞋。

额外地，除了取鞋的过程中，随时都可以从走廊取任意多双鞋（以任意顺序）入栈。

试最小化取鞋用的总时间。

输入格式

第一行，三个整数 $n,m,q$。

第二行，$q$ 个正整数 $a_1,a_2,\ldots,a_q$。

输出格式

输出一行一个正整数，表示答案。

输入输出样例 #1

输入 #1

5 1 6
2 1 2 1 2 1

输出 #1

5

输入输出样例 #2

输入 #2

6 0 4
5 4 3 4

输出 #2

17

输入输出样例 #3

输入 #3

3 2 7
1 2 3 2 3 1 3

输出 #3

4

说明/提示

样例解释

样例 $1$ 解释：第 $1$ 天时取第 $2$ 双鞋并放在走廊。穿完第 $1$ 双鞋后立刻放入栈中。不难发现这样只需要 $2+1+0+1+0+1=5$ 秒。

提示

对于 $100\%$ 的数据，保证：

• $1\le n\le 2\times 10^5$；
• $0\le m\le 2\times 10^5$；
• $1 \le q\le 10^6$；
• $1\le a_i\le n$。

子任务编号	$n,m\le$	$q\le$	特殊性质	得分
$1$	$10^3$			$17$
$2$	$2\times 10^5$	$10^6$	A	$27$
$3$			B	$37$
$4$		$2\times 10^5$		$24$
$5$		$10^6$		$15$

• 特殊性质 A：$n=m$。
• 特殊性质 B：$m=0$。

#5721. 「COCI 2024/2025 #4」Cipele

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #4 T4「Cipele」

Lana 有 $n$ 双鞋，编号从 $1$ 到 $n$。所有的鞋子都存放在一个深衣柜里。编号为 $1$ 的鞋子最初位于衣柜顶部（靠近门的位置），而编号为 $n$ 的鞋子则位于底部（离门最远的位置）。

在接下来的 $q$ 天里，Lana 在第 $i$ 天想要穿编号为 $a_{i}$ 的鞋子。为了从衣柜中取出一双鞋，若要取出目标鞋子，她必须先移开所有比它更靠近门的鞋子。取出目标鞋子后，若要将其他移出的鞋子放回衣柜，她会按照它们原有的顺序将其归位。从衣柜中取出一双鞋需要 $1$ 秒，而将鞋子放回衣柜则不需要额外的时间。

在一天的结束时，Lana 会脱下鞋子，并面临以下两种选择：

• 将它们放回衣柜的最顶部；
• 若走廊还有空位，则将它们留在走廊里。

走廊最多可以容纳 $m$ 双鞋。此外，Lana 可以在任何时间（正在取鞋的过程除外）将任何鞋子从走廊移至衣柜的最顶部。若在一天开始时目标鞋子已经在走廊里，Lana 就可以直接穿上它们，而无需花费任何取鞋时间。

Lana 非常忙碌，她希望将从衣柜取鞋的总时间降至最低。请帮她确定在接下来的 $q$ 天中，取鞋所需的最短总时间！

输入格式

第一行包含三个整数 $n, m$ 和 $q$ $(1 \leq n \leq 2 \cdot 10^{5}, 0 \leq m \leq 2 \cdot 10^{5}, 1 \leq q \leq 10^{6})$，分别代表鞋子的数量、走廊的空位数以及总天数。

第二行包含 $q$ 个整数 $a_{i}$ $(1 \leq a_{i} \leq n)$，代表 Lana 在第 $i$ 天想要穿的鞋子编号。

输出格式

在一行中输出在所有 $q$ 天内取鞋所需的最短总时间。

样例 1

输入

5 1 6
2 1 2 1 2 1

输出

5

第一天，Lana 将从衣柜中取出编号为 $2$ 的鞋子。这一动作将花费她 $2$ 秒。在一天结束时，她会将这些鞋子留在走廊里并一直保存在那里。

现在，每当她需要从衣柜中取出编号为 $1$ 的鞋子时，将花费她 $1$ 秒。然而，若她需要编号为 $2$ 的鞋子，她可以直接从走廊穿上它们而无需花费任何时间。

她取鞋花费的总时间为：$2+1+0+1+0+1=5$ 秒。

样例 2

输入

6 0 4
5 4 3 4

输出

17

样例 3

输入

3 2 7
1 2 3 2 3 1 3

输出

4

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$17$	$n, m, q \leq 1000$
$2$	$27$	$n=m$
$3$	$37$	$m=0$
$4$	$24$	$q \leq 2 \cdot 10^{5}$
$5$	$15$	无附加限制