#P12055. [2024年联测]射击

    ID: 11204 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600图论拓扑排序贪心线段树DAG-DP数据结构

[2024年联测]射击

射击(shoot)

题目描述

身为邮电部诗人的小 AA 和小 BB 正在靶场完成他们的射击任务,所有的靶子排成一列并且高度 hh 为一个 nn 阶排列。

可惜由于小 AA 和 小 BB 的枪太马了,任务进度十分缓慢,所以小 AA 和小 BB 决定携手合作共同完成任务。

在每一轮中,小 AA 和小 BB 会分别选择一个高度 xx 和 yy射出子弹,然后击倒从左往右第一个高度大于等于 xx 和第一个大于等于 yy的靶子。

需要注意的是若两颗击中的是同一个靶子,则只会有一个靶子倒下。倒下的靶子不会被击中。

小 AA 和小 BB 不仅想知道最少要经过多少轮才能击倒所有的靶子完成任务,还想知道每一轮两人子弹射出的高度。

输入格式

第一行一个正整数 nn,分别表示靶子个数。

第二行 nn 个正整数,表示靶子的高度。

输出格式

第一行一个数字 kk,表示最少射击轮数。 接下来 kk 行,每行两个数分别表示小 AA 和小 BB 这一轮射出子弹的高度。

输入输出样例 1

shoot1.in shoot1.out
8
4 3 8 2 1 7 6 5
4
4 8
3 7
2 6
1 5

说明/提示

样例解释:

第一轮射击之后,序列变为 [0,3,0,2,1,7,6,5][0,3,0,2,1,7,6,5]。 第二轮射击之后,序列变为 [0,0,0,2,1,0,6,5][0,0,0,2,1,0,6,5]。 第三轮射击之后,序列变为 [0,0,0,0,1,0,0,5][0,0,0,0,1,0,0,5]。 第四轮射击之后,序列变为 [0,0,0,0,0,0,0,0][0,0,0,0,0,0,0,0]。 所以得靶子都被击倒了,任务结束。

数据范围:

子任务编号 分值 特殊性质
subtask 1\texttt{subtask 1} 1010 n≤8n\le 8
subtask 2\texttt{subtask 2} n≤16n\le 16
subtask 3\texttt{subtask 3} 1515 n≤50n\le 50
subtask 4\texttt{subtask 4} hh 在所有排列中等概率生成
subtask 5\texttt{subtask 5} n≤500n \le 500
subtask 6\texttt{subtask 6} n≤2000n \le 2000
subtask 7\texttt{subtask 7} 2020 无

对于全部的数据,1≤n≤1000001 \le n\le 100000,1≤hi≤n1 \le h_i \le n。