957D

向右看齐 2022-05-28 02:39 117阅读 0赞

## 题意: ##

Arkady对一条河进行了n天的观察，每天的水平面高度是个数值。Arkady每天将水平面的高度在海岸上做上记号（如果原先这个位置没有记号的话），记号不会消失。Arkady将第i天看到的，位于水平面上方（不包括水平面）的记号个数mi  m i 记录到本子上。  
定义di  d i 表示第i天位于水平面下方(不包括水平面)的记号个数，你的任务即是求在可行的情况下最小的∑di  ∑ d i

## 输入格式： ##

第一行1个整数n(1 ≤ n ≤ 105)  ( 1   ≤   n   ≤   10 5 ) ,表示天数  
第二行包含n个整数m1, m2, ..., mn(0 ≤ Ei<i)  m 1 ,   m 2 ,   . . . ,   m n ( 0   ≤   E i < i )

## 输出格式: ##

仅一个整数，即最小的∑di  ∑ d i

## 样例 ##

inputCopy
    6
    0 1 0 3 0 2
    output
    6

inputCopy
    5
    0 1 2 1 2
    output
    1

inputCopy
    5
    0 1 1 2 2
    output
    0

## note: ##

在第一个示例中，下图显示了一个最佳情况。  
![0607642fa9959a6408920baa3c3cd0ec39b85b49.png][]  
请注意，在第3天，应创建一个新标记，因为如果不是，则第4天的水面上不能有3个标记。水下标记总数为0 + 0 + 2 + 0 + 3 + 1 = 6。

在第二个例子中，下图显示了一个最佳情况。  
![22b590d0a06e42e28120bc88b29128ee6fc660ae.png][]

[0607642fa9959a6408920baa3c3cd0ec39b85b49.png]: /images/20220528/b888fbd3221847bba98b90f6e3adbac4.png
[22b590d0a06e42e28120bc88b29128ee6fc660ae.png]: /images/20220528/fa38999048154aa9980d93e54b5086d5.png

发表评论取消回复

表情：

评论列表（有 0 条评论，117人围观）

还没有评论，来说两句吧...

相关阅读

相关 ZR#957

ZR\957 解法： > 首先 $ T $ 必须得要是 $ S $ 的子序列，不然不存在好的下标序列，因此一定无解。 > 考虑判断一个串 $ T $ 是...

痛定思痛。/ 2024年04月20日 10:34/ 0 赞/ 83 阅读

相关 957. N 天后的牢房

8 间牢房排成一排，每间牢房不是有人住就是空着。每天，无论牢房是被占用或空置，都会根据以下规则进行更改：如果一间牢房的两个相邻的房间都被占用或都是空的，那么该牢房

墨蓝/ 2023年10月04日 09:05/ 0 赞/ 30 阅读

相关 ZROI#957

ZROI\957 [ZROI\957][ZROI_957] 难吗?倒不是很难. 为啥考场上没做出来?菜! 为啥菜?不知道...(知道了就不这么菜了) (灵

爱被打了一巴掌/ 2023年06月02日 11:59/ 0 赞/ 16 阅读

相关【React】957- 一文总结 React Hooks 常用场景

![0d24b48bbbec3e78d8e04a983069451c.png][] > 作者：超级英雄｜原文地址: https://juejin.cn/post/691889

系统管理员/ 2023年01月21日 07:20/ 0 赞/ 14 阅读

相关 957E

题意: Arkady在一个有n架飞机的机场做交管员。飞机的移动可以看做是在一维坐标系上，Arkady的站台位于原点（0坐标）。第i架飞机位于xi x i 坐标，以速度v

Bertha 。/ 2022年05月28日 02:39/ 0 赞/ 127 阅读

相关 957D

题意: Arkady对一条河进行了n天的观察，每天的水平面高度是个数值。Arkady每天将水平面的高度在海岸上做上记号（如果原先这个位置没有记号的话），记号不会消失。Ar

向右看齐/ 2022年05月28日 02:39/ 0 赞/ 118 阅读

相关 957C

题意: 给你一个数列E,保证E1<E2<E3<...<En。 E , 保证 E 1 < E 2 < E 3 < . . . < E n 。请你选出3个数Ei<

悠悠/ 2022年05月28日 02:39/ 0 赞/ 93 阅读

相关 957B

题意: 有一张初始全是白色的N\M的格子图 Arkady可以进行一系列的操作，第i个操作包含一个非空行号集合Ri R i ，以及一个非空列号集合Ci C i 。对

迷南。/ 2022年05月28日 02:38/ 0 赞/ 97 阅读

相关逆序对 Contact ATC:CodeForces - 957E 924D 472div2

题目: [Contact ATC:CodeForces - 957E ][Contact ATC_CodeForces - 957E] 题意: Arkady在一个

傷城~/ 2022年05月28日 01:08/ 0 赞/ 120 阅读

相关推导 Riverside Curio:CodeForces - 957D 924C 472div2

题目: [Riverside Curio:CodeForces - 957D ][Riverside Curio_CodeForces - 957D] 题意: A

柔光的暖阳◎/ 2022年05月28日 00:28/ 0 赞/ 97 阅读