快乐的一天从AC开始 | 20210724 | P4754

题目链接

连续自闭一周后,短暂的快乐周末,然而上海在台风,不能出去快乐了。

(上一周欠的之后慢慢补吧

心路历程

因为小B的操作确定了,小A的操作可以直接贪,就还比较简单。

思路

二分小B操作了多少个回合。小B操作的越多,小A操作数非降,满足单调性。

验证就是小B操作了这么多回合之后,小A至少要花的回合数小于下一次小B操作的回合。

对于小A的操作,肯定是从最左或者最右开始操作,遇到要操作的地方就操作,这样很容易得到至少要花的回合数。

具体其实就是区间加,单点求值。可以线段树,可以树状数组,这样是\(O(n\log n\log m )\)的。

但是其实做到\(O( n \log n)\),就检查的时候可以线性:左端点加,右端点减,记录前缀增量,把他加到当前元素上,就可以做到区间加和单点求值。

最后再算一次至少要花的回合数。

上一篇:4-STM32物联网开发WIFI(ESP8266)+GPRS(Air202)系统方案数据篇(云端电脑(Windows)安装配置数据库,使用本地Navicat for MySQL和手机APP 远程连接测试)


下一篇:Python学习day5作业