比赛简介
- 题数:4道
- 时间:3个小时
- 总分:400分
- 难度:2道J2,2道S2
- 晋级标准:前100名
开始考试
先来讲题。
A题签到题忽略…… CD题目前没能力解决,也忽略。
B:Mila的木棍
题面
$\text{Mila}$ 找到了 $n$ 根木棍,她将这 $n$ 根木棍排成一行形成一个序列 $a$,但是她发现此时的序列可能是不优美的。
假如木棍的长度从左到右形成一个不下降序列,那么 $\text{Mila}$ 认为这些木棍才是优美的。因此,$\text{Mila}$ 学习了一种可以削减木棍长度的魔法:对一个区间 $[l,r]$ 使用一次魔法,可以将这个区间内所有木棍的长度减 $1$。
不下降序列:对于所有 $1\leq j < i \leq n$,满足 $a[j] \leq a[i]$。例如序列 $3,3,4,5$ 就是不下降序列。
现在 $\text{Mila}$ 想要知道:至少需要使用多少次魔法才可以将这些木棍变得优美?
输入格式
第一行一个整数 $n$,表示木棍的数量。
第二行 $n$ 个以空格隔开的整数,表示这个序列,第 $i$ 根木棍的长度为 $a_i$。
输出格式
输出共一行一个整数,表示答案。
数据范围
对于 $20%$ 的数据,满足 $n,a_i\leq 10$。
对于 $40%$ 的数据,满足 $n\leq 10^3$。
对于另外 $20%$ 的数据,保证 $a$ 是一个不递增序列。
对于 $100%$ 的数据,满足 $1\leq n\leq 10^6,1\leq a_i\leq 10^9$。
样例输入
|
|
样例输出
|
|
满分解
对于一个$i$,如果$a_i \gt a_{i + 1}$,那么为了形成不下降序列,至少有$a_i - a_{i + 1}$次削减的区间的右端点需位于$i$。
所以操作数至少为$\sum_{i=1}^{n - 1} max(a_i - a_{i + 1}, 0)$。
|
|
总结
要用草稿纸
不用草稿纸基本只能做签到题,况且这场比赛难度确实不低。