当前位置: 首页 > news >正文

[Poetize6] IncDec Sequence

题目描述

给定一个长度为n的数列a1,a2,⋯,an每次可以选择一个区间[l,r]使这个区间内的数都加1或者都减1

请问至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。

题解

经典差分题目。

区间加减——>差分变成单点加减

每次一个位置+1,一个位置-1

广义差分,b[1]=a[1],b[i>2]=a[i]-a[i-1]

除b[1]要让所有都变成0

b[1]的种类数即为方案数。

为了使方案数最少,可以每次把负数点+1,正数点-1,改变为2

正数和p,负数和q(绝对值)

所以,消去正数、负数较少的那一个的操作次数就是min(p,q)

然后,正数、负数较多的那一个可能剩下。

假设正数剩的多,

那么现在实际上是一个阶梯形状,从左到右递增。

这个时候,为了保证次数最少,每次消除必然要使正数(设位置是pos)-1

那,哪个数+1呢?可以是b[1],象征对1~pos 区间+1,

可以是b[n+1]象征对pos~n区间-1

所以,每次选择可以多一个b[1],而且也能保证最少操作次数。

所以,ans=max(p,q)为答案。

ans-min(p,q)是方案数。

转载于:https://www.cnblogs.com/Miracevin/p/9676616.html

相关文章:

  • Springboot+mybatis整合
  • Django中引入Highcharts
  • 洛谷 P2152 [SDOI2009]SuperGCD (高精度)
  • Linux 基本概念 命令
  • 26. 删除排序数组中的重复项
  • golang包time用法详解
  • Android TV 开发(2)
  • 百度面试Web前端的经历,值得收藏
  • Unity配置安卓打包环境JDK和SDK下载以及配置详解
  • 删除n天前的所有目录和文件
  • 主流的消息队列MQ比较,详解MQ的4类应用场景
  • too many connections 解决方法
  • php的分层思想
  • 在aws ec2上使用root用户登录
  • nginx+tomcat+java部署总结
  • 【comparator, comparable】小总结
  • 【腾讯Bugly干货分享】从0到1打造直播 App
  • 10个最佳ES6特性 ES7与ES8的特性
  • axios请求、和返回数据拦截,统一请求报错提示_012
  • Golang-长连接-状态推送
  • go语言学习初探(一)
  • PV统计优化设计
  • Python学习之路13-记分
  • SpriteKit 技巧之添加背景图片
  • Vim Clutch | 面向脚踏板编程……
  • VUE es6技巧写法(持续更新中~~~)
  • Vue.js源码(2):初探List Rendering
  • 得到一个数组中任意X个元素的所有组合 即C(n,m)
  • 嵌入式文件系统
  • 由插件封装引出的一丢丢思考
  • 原生JS动态加载JS、CSS文件及代码脚本
  • ​​快速排序(四)——挖坑法,前后指针法与非递归
  • ​LeetCode解法汇总2583. 二叉树中的第 K 大层和
  • ​Linux Ubuntu环境下使用docker构建spark运行环境(超级详细)
  • ​软考-高级-系统架构设计师教程(清华第2版)【第12章 信息系统架构设计理论与实践(P420~465)-思维导图】​
  • (8)Linux使用C语言读取proc/stat等cpu使用数据
  • (搬运以学习)flask 上下文的实现
  • (第二周)效能测试
  • (附源码)计算机毕业设计ssm电影分享网站
  • (淘宝无限适配)手机端rem布局详解(转载非原创)
  • (转)利用ant在Mac 下自动化打包签名Android程序
  • (转)自己动手搭建Nginx+memcache+xdebug+php运行环境绿色版 For windows版
  • ***监测系统的构建(chkrootkit )
  • **PyTorch月学习计划 - 第一周;第6-7天: 自动梯度(Autograd)**
  • .Net - 类的介绍
  • .net core 3.0 linux,.NET Core 3.0 的新增功能
  • .Net core 6.0 升8.0
  • .NET 应用启用与禁用自动生成绑定重定向 (bindingRedirect),解决不同版本 dll 的依赖问题
  • .NET序列化 serializable,反序列化
  • .NET业务框架的构建
  • @Transactional类内部访问失效原因详解
  • [AutoSar]状态管理(五)Dcm与BswM、EcuM的复位实现
  • [C++] Windows中字符串函数的种类
  • [Erlang 0129] Erlang 杂记 VI 2014年10月28日
  • [IE编程] 多页面基于IE内核浏览器的代码示例