pdd Java后端 第三题 求100%的题解

n 盆花,选取[r,l]区间,将编号(到编号r的花盆中的玫瑰替换成牡丹,将牡丹替换成玫瑰。至多进行一次这样操作

求观赏度的所有种类

观赏度:玫瑰与牡丹的盆数之差的绝对值

输入描述

输入共两行:

第一行一个数字n,表示有n盆花。(1<=n<=100000)

第二行n个数字,每个数字表示花的种类,0表示玫瑰,1表示牡丹。

输出描述

输出一行,一个数字,表示经过至多一次操作后,有多少种不同的观赏度

示例 1

输入

2

0 1

输出

2

示例2

输入

4

0 1 1 0

输出

3

两层for只过了60%,求100%的题解

全部评论
把0当-1,1当1,做一个前缀和。题目就相当于,问任取两个前缀和之差有多少种。根据观察,发现相邻的绝对差永远是1,维护一个前缀最大值ma和最小值mi。再根据前面的最大最小值计算,在当前位置。使用翻转时,观赏度最大能增加多少(ma - a[i]),最大能减少多少(a[i] - mi)。最后分类讨论有多少贡献,或者直接扔进set里面,看有多少元素
1 回复 分享
发布于 08-12 10:15 广东

相关推荐

点赞 1 评论
分享
牛客网
牛客企业服务