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

100. 增减序列

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

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

输入格式

第一行输入正整数 n。

接下来 n行,每行输入一个整数,第 i+1 行的整数代表 ai。

输出格式

第一行输出最少操作次数。

第二行输出最终能得到多少种结果。

数据范围

0<n≤105
0≤ai<2147483648

输入样例:

4
1
1
2
2

输出样例:

1
2

 

差分解决一段区域同时增加或减少的问题
给区间【L,R】上都加上一个常数c,则b[L] += c , b[R + 1] -=c

求出a的差分序列b,其中b1 = a1,b(i) = a(i) - a(i - 1) (2 <= i <= n)。令b(n + 1) = 0,题目对序列a的操作,相当于每次可以选出b1,b2…b(n + 1)中的任意两个数,一个加1,另外一个减一。目标是把b2,b3,…bn变为全0。最终得到的数列a就是由 n 个 b1 构成的

任选两个数的方法可分为四类
1、2 <= i , j <=n(优先)
2、i = 1, 2 <=j <=n
3、2 <= i <= n , j = n + 1
4、i = 1, j = n + 1(没有意义)

设b2,b3....bn中正数总和为p,负数总和的绝对值为q。首先以正负数匹配的方式尽量执行1类操作,可执行min(p,q)次。剩余|p - q|个为匹对,每个可以选与b1或b(n + 1)匹配,即执行2 或 3 类操作,共需|p - q|次

综上所诉,最少操作次数为min(p,q) + |p - q|。根据|p - q|次第2、3类操作的选择情况,能产生|p - q| + 1中不同的b1的值,即最终得到的序列a可能有|p - q| + 1 种

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;constexpr int N=1e5+7;
typedef long long ll;
ll n,a[N],b[N];
int main(){scanf("%lld",&n);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);b[i]=a[i]-a[i-1];}ll zheng=0, fu=0;for(int i=2;i<=n;i++) {if (b[i] > 0) {zheng += b[i];}else if (b[i] < 0) {fu -= b[i];}}ll ans1= max(zheng ,fu);ll ans2= abs(zheng-fu)+1;printf("%lld\n", ans1);printf("%lld\n", ans2);return 0;
}

 

 

相关文章:

100. 增减序列

给定一个长度为 n 的数列 a1,a2,…,an&#xff0c;每次可以选择一个区间 [l,r]&#xff0c;使下标在这个区间内的数都加一或者都减一。 求至少需要多少次操作才能使数列中的所有数都一样&#xff0c;并求出在保证最少次数的前提下&#xff0c;最终得到的数列可能有多少种。 输入…...

操作系统之进程的初步认识(1)

进程1. 进程的相关概念1.1 进程的定义1.2 进程的概念(1)1.3 进程的概念(2)2. 进程和程序的区别3. 进程管理:3.1 进程的结构体有哪些属性(1) Pid(操作系统里指进程识别号)(2) 内存指针(3) 文件描述符表4. 进程调度:(1) 并行(2) 并发5. 进程调度需要的属性(1) 进程状态(2) 进程优…...

【Java】你真的懂封装吗?一文读懂封装-----建议收藏

博主简介&#xff1a;努力学习的预备程序媛一枚~博主主页&#xff1a; 是瑶瑶子啦所属专栏: Java岛冒险记【从小白到大佬之路】 前言 write in the front: 如何理解封装&#xff1f; 试想&#xff1a;我们使用微波炉的时候&#xff0c;只用设置好时间&#xff0c;按下“开始”…...

使用MobaXterm ssh远程登录Ubuntu 20.04

使用MobaXterm 远程登录Ubuntu 20.04 首先需要到官网下载一个MobaXterm 准备一台Ubuntu20.04的虚拟机。使用ifconfig查看IP 我这里的虚拟机是新安装的&#xff0c;所以会提示命令不存在&#xff0c;只要按照提示输入&#xff1a; sudo apt install net-tools接着等待安装完成…...

蓝桥杯历年真题训练

2012年第四届全国电子专业人才设计与技能大赛“自动售水机”设计任务书1. 系统框图接下来我们将任务分块&#xff1a; 1. 按键控制单元 设定按键 S7 为出水控制按键&#xff0c;当 S7 按下后&#xff0c;售水机持续出水&#xff08;继电器接通&#xff0c;指示 灯 L10 点亮&…...

Spring事务报错: org.springframework.transaction.UnexpectedRollbackException

异常信息&#xff1a;支持当前事务&#xff0c;如果不存在则抛出异常。事务被回滚&#xff0c;因为它被标记为仅回滚 org.springframework.transaction.UnexpectedRollbackException: Transaction rolled back because it has been marked as rollback-onlyat org.springframe…...

Spring:IOC和AOP

Spring&#xff1a;IOC和AOP一. IOC(1) 引入(2) 定义(3) 作用(4) 实现(5) DI依赖注入二. AOP(1) 概念(2) Spring中的AOP(3) 入门案例0. 准备&#xff1a;1. 定义通知类和通知方法&#xff1b;2. 在通知类中描述和定义切入点 pointcut3. 用注释绑定切入点和通知方法4. 通知类&am…...

【笔记】效率之门——Python中的函数式编程技巧

文章目录Python函数式编程1. 数据2. 推导式3. 函数式编程3.1. Lambda函数3.2. python内置函数3.3. 高阶函数4. 函数式编程的应用Python函数式编程 我的AI Studio项目&#xff1a;【笔记】LearnDL第三课&#xff1a;Python高级编程——抽象与封装 - 飞桨AI Studio (baidu.com) p…...

Java【多线程基础2】 Thread类 及其常用方法

文章目录前言一、Thread类1, 构造方法2, 常用成员属性3, 常用成员方法3.1, start 启动线程3.2, interrupt 中断线程 (重点)3.2.1, 手动设置标记位3.2.2, 使用内置标记位3.3.3, interrupt 方法 的作用3.3 sleep 休眠线程3.4, jion 等待线程3.5 获取当前线程的引用总结前言 各位读…...

JVM调优实战及常量池详解

目录 阿里巴巴Arthas详解 Arthas使用场景 Arthas使用 GC日志详解 如何分析GC日志 CMS G1...

ChatGPT研究分析:GPT-4做了什么

前脚刚研究了一轮GPT3.5&#xff0c;OpenAI很快就升级了GPT-4&#xff0c;整体表现有进一步提升。追赶一下潮流&#xff0c;研究研究GPT-4干了啥。本文内容全部源于对OpenAI公开的技术报告的解读&#xff0c;通篇以PR效果为主&#xff0c;实际内容不多。主要强调的工作&#xf…...

我为什么要写博客,写博客的意义是什么??

曾经何时我也不知道&#xff0c;怎样才能变成我自己所羡慕的大佬&#xff01;&#xff01;在一次次的CSDN阅读的过程中&#xff0c;结实了许多志同道合的人&#xff01;&#xff01;包过凉哥&#xff0c;擦姐……大佬&#xff0c;但是&#xff0c;很遗憾&#xff0c;与这些人只…...

ssm框架之spring:浅聊AOP

AOP&#xff08;Aspect Oriented Programming&#xff09;&#xff0c;是一种设计思想。先看一下百度百科的解释&#xff1a; 在软件业&#xff0c;AOP为Aspect Oriented Programming的缩写&#xff0c;意为&#xff1a;面向切面编程&#xff0c;通过预编译方式和运行期间动态…...

k8s详解

一、k8s中的yaml文件 JSON格式&#xff1a;主要用于api接口之间信息的传递YAML格式&#xff1a;主要用于配置和管理&#xff0c;YAML是一种简洁的非标记性语言&#xff0c;内容格式人性化 YAML格式&#xff1a; 大小写敏感使用缩进代表层级关系&#xff0c;不支持TAB制表符缩…...

计算机操作系统(第四版)第一章操作系统引论 1.1操作系统的目标和作用

第一章操作系统引论 1.1操作系统的目标和作用 什么是操作系统OS&#xff1f; 配置在计算机硬件上的第一层软件是对硬件的首次扩充。 是最重要的系统软件&#xff0c;其他系统软件应用软件都依赖于操作系统的支持。 操作系统主要作用&#xff1f; 管理计算机系统所有硬件设…...

git push解决办法: ! [remote rejected] master -> master (pre-receive hook declined)

项目经理远程创建了一个空项目&#xff0c;无任何内容&#xff0c;给我赋予的developer账号权限&#xff0c;本地改为后提交代码试了很多次都上传不上去&#xff0c;报错如下&#xff1a; ! [remote rejected] master -> master (pre-receive hook declined)先说结果&#x…...

jQuery 遍历方法总结

遍历方法有&#xff1a;1、add()&#xff0c;用于把元素添加到匹配元素的集合中&#xff1b;2、children()&#xff0c;用于返回被选元素的所有直接子元素&#xff1b;3、closest()&#xff0c;用于返回被选元素的第一个祖先元素&#xff1b;4、contents()&#xff0c;用于返回…...

OKHttp 源码解析(二)拦截器

游戏SDK架构设计之代码实现——网络框架 OKHttp 源码解析&#xff08;一&#xff09; OKHttp 源码解析&#xff08;二&#xff09;拦截器 前言 上一篇解读了OKHttp 的基本框架源码&#xff0c;其中 OKHttp 发送请求的核心是调用 getResponseWithInterceptorChain 构建拦截器链…...

如何修改设置浏览器内核模式

优先级&#xff1a; 强制锁定极速模式 >手动切换&#xff08;用户&#xff09;>meta指定&#xff08;开发者&#xff09;>浏览器兼容列表&#xff08;浏览器&#xff09; 需要用360安全浏览器14&#xff0c;chromium108内核&#xff0c;下载地址https://bbs.360.cn/t…...

30个Python常用小技巧

1、原地交换两个数字 1 2 3 4 x, y 10, 20 print(x, y) y, x x, y print(x, y) 10 20 20 10 2、链状比较操作符 1 2 3 n 10 print(1 < n < 20) print(1 > n < 9) True False 3、使用三元操作符来实现条件赋值 [表达式为真的返回值] if [表达式] else [表达式…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...

软件工程 期末复习

瀑布模型&#xff1a;计划 螺旋模型&#xff1a;风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合&#xff1a;模块内部功能紧密 模块之间依赖程度小 高内聚&#xff1a;指的是一个模块内部的功能应该紧密相关。换句话说&#xff0c;一个模块应当只实现单一的功能…...