问题 5044 --区间操作

5044: 区间操作

题目描述

  有一个 $n$ 个数的序列，一开始所有的数都是 $0$，每次可以将一个区间  内的数加 $[l,r] (l \leq r)$，求到达最终状态的最少操作次数。

输入

第一行包含一个正整数 $n$，表示序列的长度。
第二行包含 $n$ 个不同的正整数 $a_1,a_2,\dots,a_n$，表示最终的状态。

输出

输出的第一行是一个正整数 $m$，表示最少的操作次数。
接下来 $m$ 行每行两个正整数 $l_i,r_i$，表示一次操作的区间。
这 $m$ 个区间需要以 $l$ 为第一关键字，以 $r$ 为第二关键字，从小到大输出。

样例输入输出

输入#1 复制 
6
1 2 4 6 2 1
输出#1 复制 
6
1 6
2 5
3 4
3 4
4 4
4 4

提示

对于 $10\%$ 的数据，$n \leq 4$。
对于 $30\%$ 的数据，$n \leq 200$。
对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^5$。

发表题解
序号 标题 作者 发表时间 费用 订购数 操作

题目信息

提交
难度
普及+/提高-
标签
点击显示
递交数
4
已通过
1
通过率
25%
时间限制
1 秒
内存限制
512 MB
来源
2020CSP模拟A10
收藏