P11665 [JOI 2025 Final] 只不过是长的领带 2 / Just Long Neckties 2

题目背景

译自 第24回日本情報オリンピック 本選 T4。

题目描述

有一个长度为 $k$（$k\ge 1$）的正整数数列 $B_1,\cdots,B_k$，初始 $B_i=1$（$1\le i\le k$）。这里，$k$ 是一个还未确定的数。

有 $N$ 场演出，第 $i$（$1\le i\le N$）场演出中，观众将会报出数字 $A_i$。然后你需要做以下的事情：

• 选择是否回应这个观众。
  • 如果选择回应，你需要选择 $j$（$1\le j\le k$）满足 $B_j\le A_i$，然后令 $B_j\gets A_i$。（注意这里是小于等于号。）
    • 如果无法选择这样的 $j$，则演出失败。
  • 否则，不需要做任何事。

然而，如果连续两次（或者更多次）选择不回应观众，观众会生气，从而演出失败。

在演出不失败的前提下，确定 $k$ 的最小值。

输入格式

如下所示：

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

输出格式

输出一行一个正整数，表示满足条件的 $k$ 的最小值。

输入输出样例 #1

输入 #1

5
5 3 4 2 1

输出 #1

2

输入输出样例 #2

输入 #2

6
2 1 1 2 2 1

输出 #2

1

输入输出样例 #3

输入 #3

10
2 4 6 7 4 5 5 3 4 1

输出 #3

3

说明/提示

样例解释

样例 $1$ 解释

$k=2$ 时，在五次演出中分别选择：

• 不回应；
• 回应，$j=1$（此后 $B_1\gets 3$）；
• 回应，$j=1$（此后 $B_1\gets 4$）；
• 回应，$j=2$（此后 $B_2\gets 2$）；
• 不回应；

可以证明 $k=1$ 时演出必定失败。所以输出 $2$。

该样例满足子任务 $1,3\sim 7$ 的限制。

样例 $2$ 解释

$k=1$ 时，在第 $1,6$ 个演出时选择不回应即可。

该样例满足所有子任务的限制。

样例 $3$ 解释

该样例满足子任务 $1,4\sim 7$ 的限制。

数据范围

• $2\le N\le 5\times 10^6$。
• $1\le A_i\le 21$（$1\le i\le N$）。
• 输入的值全部是整数。

子任务

1. （10pts）$N\le 15$。
2. （6pts）$N\le 500$，$A_i\le 2$（$1\le i\le N$）。
3. （12pts）$N\le 500$，$A_i\le 5$（$1\le i\le N$）。
4. （18pts）$N\le 500$，$A_i\le 15$（$1\le i\le N$）。
5. （26pts）$N\le 5\times 10^5$，$A_i\le 15$（$1\le i\le N$）。
6. （10pts）$N\le 5\times 10^5$。
7. （18pts）无额外限制。

[AdditionalFile4776.zip](file://AdditionalFile4776.zip?type=additional_file)

#4776. 「JOI 2025 Final」仅仅长的领带 2

标签: 传统 | 时间限制: 3000 ms | 内存限制: 2048 MiB |

题目描述

题目译自 JOI 2025 Final T4 「長いだけのネクタイ 2 / Just Long Neckties 2」

Just Odd Inventions 公司以发明「仅仅奇怪的东西（just odd inventions）」而闻名。这里简称为 JOI 公司。

为了纪念其畅销产品「仅仅长的领带」上市五周年，JOI 公司开发了一款全新的「无限长的领带」。这种新型领带的特点是可以无限延长。

JOI 公司决定举办一个发布会来宣传这款新型领带，并邀请你担任主持人。在发布会上，几位穿着新型领带的模特将会登台亮相。最初，每位模特的领带长度都是 $1$。

随后，你需要进行 $N$ 次表演，让观众亲身体验领带长度可调的功能。每次表演按照以下步骤进行：

1. 首先，观众说出一个他们喜欢的数字，我们称这个数字为 $x$。
2. 然后，你可以选择回应或者忽略这个数字。
   • 如果你选择回应，你需要从登台的模特中选择一个领带长度不超过 $x$ 的模特，并将其领带长度调整为 $x$（注意，选择的模特的领带长度可以已经是 $x$）。如果没有一个合适的模特可以选择，发布会将失败。
   • 如果你选择忽略，你什么也不做。 但是，如果连续两次或以上忽略观众说出的数字，观众会不满意，发布会将失败。

登台的模特数量 $k$ $(k \geq 1)$ 尚未决定，但由于雇用模特需要花费，$k$ 越小越好。为了避免发布会失败，需要的模特数量取决于每次表演中观众说出的数字。你可以预见在第 $i$ $(1 \leq i \leq N)$ 次表演中，观众会说出的数字是 $A_i$。

编写一个程序，在给定发布会中观众会说出的数字信息时，计算出避免发布会失败所需的最小模特数量 $k$。

输入格式

第一行包含一个整数 $N$。

第二行包含用空格分隔的 $N$ 个整数 $A_1, A_2, \ldots A_N$。

输出格式

输出避免发布会失败所需的最小模特数量 $k$。

样例 1

输入

5
5 3 4 2 1

输出

2

当 $k=2$ 时，可以按照以下方式进行发布会：

• 首先，穿着新型领带的两位模特登台。最初，每位模特的领带长度都是 $1$。
• 第一次表演时，观众说出数字 $5$。你忽略这个数字。
• 第二次表演时，观众说出数字 $3$。你回应这个数字，并将第一位模特的领带长度调整为 $3$。此时，两位模特的领带长度分别为 $3$ 和 $1$。
• 第三次表演时，观众说出数字 $4$。你回应这个数字，并将第一位模特的领带长度调整为 $4$。此时，两位模特的领带长度分别为 $4$ 和 $1$。
• 第四次表演时，观众说出数字 $2$。你回应这个数字，并将第二位模特的领带长度调整为 $2$。此时，两位模特的领带长度分别为 $4$ 和 $2$。
• 第五次表演时，观众说出数字 $1$。你忽略这个数字。

如果 $k=1$，发布会必将失败。例如，如果按照上述方式在第二、三、四次表演中回应观众说出的数字，那么在第三次表演结束时，唯一登台的模特的领带长度将是 $4$。在第四次表演时，没有模特的领带长度不超过 $2$，因此发布会将失败。

因此，避免发布会失败所需的最小模特数量为 $2$。

这个样例满足子任务 $1,3,4,5,6,7$ 的限制。

样例 2

输入

6
2 1 1 2 2 1

输出

1

当 $k=1$ 时，可以按照以下方式进行发布会：

• 首先，穿着新型领带的一位模特登台。最初，模特的领带长度是 $1$。
• 第一次表演时，观众说出数字 $2$。你忽略这个数字。
• 第二次表演时，观众说出数字 $1$。你回应这个数字，并将登台模特的领带长度调整为 $1$。
• 第三次表演时，观众说出数字 $1$。你回应这个数字，并将登台模特的领带长度调整为 $1$。
• 第四次表演时，观众说出数字 $2$。你回应这个数字，并将登台模特的领带长度调整为 $2$。
• 第五次表演时，观众说出数字 $2$。你回应这个数字，并将登台模特的领带长度调整为 $2$。
• 第六次表演时，观众说出数字 $1$。你忽略这个数字。

因此，避免发布会失败所需的最小模特数量为 $1$。

这个样例满足所有子任务的限制。

样例 3

输入

10
2 4 6 7 4 5 5 3 4 1

输出

3

这个样例满足子任务 $1,4,5,6,7$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 5000000$。
• $1 \leq A_i \leq 21$ $(1 \leq i \leq N)$。
• 输入的所有值均为整数。

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

子任务	分值	附加限制
$1$	$10$	$N \leq 15$
$2$	$6$	$N \leq 500, A_i \leq 2\,(1 \leq i \leq N)$
$3$	$12$	$N \leq 500, A_i \leq 5\,(1 \leq i \leq N)$
$4$	$18$	$N \leq 500, A_i \leq 15\,(1 \leq i \leq N)$
$5$	$26$	$N \leq 500000, A_i \leq 15\,(1 \leq i \leq N)$
$6$	$10$	$N \leq 500000$
$7$	$18$	无附加限制