当前位置: 首页 > 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 [表达式…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

Windows 下端口占用排查与释放全攻略

Windows 下端口占用排查与释放全攻略​ 在开发和运维过程中&#xff0c;经常会遇到端口被占用的问题&#xff08;如 8080、3306 等常用端口&#xff09;。本文将详细介绍如何通过命令行和图形化界面快速定位并释放被占用的端口&#xff0c;帮助你高效解决此类问题。​ 一、准…...

在Spring Boot中集成RabbitMQ的完整指南

前言 在现代微服务架构中&#xff0c;消息队列&#xff08;Message Queue&#xff09;是实现异步通信、解耦系统组件的重要工具。RabbitMQ 是一个流行的消息中间件&#xff0c;支持多种消息协议&#xff0c;具有高可靠性和可扩展性。 本博客将详细介绍如何在 Spring Boot 项目…...

6.9本日总结

一、英语 复习默写list11list18&#xff0c;订正07年第3篇阅读 二、数学 学习线代第一讲&#xff0c;写15讲课后题 三、408 学习计组第二章&#xff0c;写计组习题 四、总结 明天结束线代第一章和计组第二章 五、明日计划 英语&#xff1a;复习l默写sit12list17&#…...

Pandas 可视化集成:数据科学家的高效绘图指南

为什么选择 Pandas 进行数据可视化&#xff1f; 在数据科学和分析领域&#xff0c;可视化是理解数据、发现模式和传达见解的关键步骤。Python 生态系统提供了多种可视化工具&#xff0c;如 Matplotlib、Seaborn、Plotly 等&#xff0c;但 Pandas 内置的可视化功能因其与数据结…...