构造回文数组

目录

原题描述:

题目描述

时间:1s 空间:256M

题目描述:

输入格式:

输出格式:

样例1输入:

样例1输出:

样例2输入:

样例2输出:

约定:

作者hack数据:

输入:

输出:

主要思路:

求答案:

代码code:


原题描述:

时间限制: 1000ms

空间限制: 262144kB

题目描述

时间:1s 空间:256M

题目描述:

小信有一个长度为 n 的数组 a,他想把这个数组变成回文数组。

他可以操作若干次,每次操作,选择一个区间[L,R],把a_L,a_{L+1},...a_R​ 都加 1

小信想知道最少需要操作多少次,才能把这个数组变成回文数组。

输入格式:

第一行包含一个整数 n

第二行包含长度为 n 的数组 a_1,a_2,...a_n​ 。

输出格式:

输出一个整数表示答案。

样例1输入:

6
2 6 4 3 4 1

样例1输出:

2

样例2输入:

3
1 10 1

样例2输出:

0

约定:

对于100%的数据,1\le n\le 3 \cdot 10^5,1 \le a_i \le 10^9

对于样例1:选择 [3,6]和 [4,5],数组变成 [2,6,5,5,6,2]

作者hack数据:


输入:
 

100
295117793 852883521 36092583 681745569 23541647 32480206 769047426 128111255 850655575 8867194 368297902 613812293 347992953 134986353 863972512 970426966 785192811 540559474 988288563 456754809 154127192 76979571 460304832 733713409 70970660 635551742 769915887 7641407 660822912 748447793 598826955 609365172 822558626 849292246 849242098 941529514 216622499 647819205 34288562 360796801 564768544 688079849 702507270 777507089 776688905 515137821 52246637 307838702 453802754 136279521 618645584 803000735 877721915 194107657 136422627 187654402 227004447 519370751 457822037 804058036 911179942 457248799 305969878 787934175 14313040 9582663 34547015 870503865 216036366 15134170 174645568 77155278 213349935 622731147 84032183 14391789 46136215 862980910 139514947 73594405 599740219 178453695 493364413 239940662 981248295 136272953 532638230 679826619 820419790 652179351 81724392 185039813 238018126 660954049 903887251 617400394 816543430 957422974 272333302 464554507

输出:

12198773018

主要思路:

这个是个贪心题目,看了我的hack数据,我们也要知道,这题要开:long long!!!

我们可以这样想,因为只加不减,所以可以从原数组中,相对的两个(a[i]相对a[n-i+1])

如果a[i]大,那么a[i]就不需要被加,sum[i] = 0,a[n-i+1]就要被加a[i]-a[n-i+1]次,sum[n-i+1] = a[i]-a[n-i+1] 

反之亦然。

sum[i]就代表了这个数字要加几次才可以和他相对的数字相等。

求答案:

上面的这些话是初始化,现在我们要求答案,我们可以找一找规律。

用样例1来说。

sum数组={0,0,0,1,2,1}

我们不看0。

看后边的1,2,1。

如何可以发现规律?

如果只有1,那么最少操作一次。

如果只有1,2,那么最少操作两次。

如果只有1,2,1还是操作两次。

有些同学会很快发现规律:最少操作数就是sum连续一段区间的最大值。

那么我告诉你:恭喜你,猜错了。

sum反例:1,2,1,3。

这个时候,答案应该是4,而按上面的方式,答案是3。

所以正确结论是:

如果sum[i]>sum[i-1],那么ans+=sum[i]-sum[i-1]

如果sum[i]<sum[i-1],那么答案不变。

代码code:

理解上面的话后,就好写了。

#include<bits/stdc++.h>
using namespace std;
int n;
int a[300010];
int sum[300010];
int main()
{cin>>n;//输入for(int i=1;i<=n;i++){cin>>a[i];}
//	int ret=0;//初始化for(int i=1,j=n;i<=n,j>=1;i++,j--){if(a[i]>=a[j]){sum[i] = 0;sum[j] = a[i]-a[j];}else {sum[i] = a[j]-a[i];sum[j] = 0;}
//		cout<<sum[i];}//算答案long long ret=0;for(int i=1;i<=n;i++){if(sum[i]>=sum[i-1]){ret+=sum[i]-sum[i-1];}}cout<<ret;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/254194.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

《幻兽帕鲁》攻略:0基础入门及游戏基础操作 幻兽帕鲁基础设施 幻兽帕鲁基础攻击力 Mac苹果电脑玩幻兽帕鲁 幻兽帕鲁加班加点

今天就跟大家聊聊《幻兽帕鲁》攻略&#xff1a;0基础入门及游戏基础操作。 如果想在苹果电脑玩《幻兽帕鲁》记得安装CrossOver哦。 以下纯干货&#xff1a; CrossOver正版安装包&#xff08;免费试用&#xff09;&#xff1a;https://souurl.cn/Y1gDao 一、基础操作 二、界面…

(45)执行操作后的变量值

文章目录 每日一言题目解题思路代码结语 每日一言 与其临渊羡鱼&#xff0c;不如退而结网。——《史记汉书董仲舒传》 题目 题目链接&#xff1a;执行操作后的变量值 存在一种仅支持 4 种操作和 1 个变量 X 的编程语言&#xff1a; X 和 X 使变量 X 的值 加 1 –X 和 X-- 使…

Allegro如何把Symbols,shapes,vias,Clines,Cline segs等多种元素一起移动

Allegro如何把Symbols,shapes,vias,Clines,Cline segs等多种元素一起移动 在用Allegro进行PCB设计时,有时候需要同时移动某个区域的所有元素,如:Symbols,shapes,vias,Clines,Cline segs等元素。那么如何操作呢? 首先就是把Symbols,shapes,vias,Clines,Cline …

【机器学习笔记】机器学习基本概念

机器学习基本概念 文章目录 机器学习基本概念1 概述2 机器学习实验方法与原则2.1 平均指标 2.2 训练集、验证集与测试集2.3 随机重复实验2.4 K折交叉验证2.4 统计有效性检验 1 概述 什么是机器学习 —— 在某种任务上基于经验不断进步 T (Task)&#xff1a;需要解决什么任务 P(…

LLaMA 模型中的Transformer架构变化

目录 1. 前置层归一化&#xff08;Pre-normalization&#xff09; 2. RMSNorm 归一化函数 3. SwiGLU 激活函数 4. 旋转位置嵌入&#xff08;RoPE&#xff09; 5. 注意力机制优化 6. Group Query Attention 7. 模型规模和训练超参数 8. 分布式模型训练 前置归一化与后置…

改进神经网络

Improve NN 文章目录 Improve NNtrain/dev/test setBias/Variancebasic recipeRegularizationLogistic RegressionNeural networkother ways optimization problemNormalizing inputsvanishing/exploding gradientsweight initializegradient checkNumerical approximationgrad…

设计模式-行为型模式(下)

1.访问者模式 访问者模式在实际开发中使用的非常少,因为它比较难以实现并且应用该模式肯能会导致代码的可读性变差,可维护性变差,在没有特别必要的情况下,不建议使用访问者模式. 访问者模式(Visitor Pattern) 的原始定义是&#xff1a; 允许在运行时将一个或多个操作应用于一…

【华为云】云上两地三中心实践实操

写在前面 应用上云之后&#xff0c;如何进行数据可靠性以及业务连续性的保障是非常关键的&#xff0c;通过华为云云上两地三中心方案了解相关方案认证地址&#xff1a;https://connect.huaweicloud.com/courses/learn/course-v1:HuaweiXCBUCNXI057Self-paced/about当前内容为华…

react将选中文本自动滑动到容器可视区域内

// 自动滚动到可视区域内useEffect(() > {const target ref;const wrapper wrapperRef?.current;if (target && wrapperRef) {const rect target.getBoundingClientRect();const wrapperRect wrapper.getBoundingClientRect();const isVisible rect.bottom &l…

2. Maven 继承与聚合

目录 2. 2.1 继承 2.2继承关系 2.2.1 思路分析 2.2.2 实现 2.1.2 版本锁定 2.1.2.1 场景 2.1.2.2 介绍 2.1.2.3 实现 2.1.2.4 属性配置 2.2 聚合 2.2.1 介绍 2.2.2 实现 2.3 继承与聚合对比 maven1&#xff1a;分模块设计开发 2. 在项目分模块开发之后啊&#x…

查大数据检测到风险等级太高是怎么回事?

随着金融风控越来越多元化&#xff0c;大数据作为新兴的技术被运用到贷前风控中去了&#xff0c;不少人也了解过自己的大数据&#xff0c;但是由于相关知识不足&#xff0c;看不懂报告&#xff0c;在常见的问题中&#xff0c;大数据检测到风险等级太高是怎么回事呢?小易大数据…

吉他学习:C大调第一把位音阶,四四拍曲目练习 小星星

第十三课 C大调第一把位音阶https://m.lizhiweike.com/lecture2/29364198 第十四课 四四拍曲目练习 小星星https://m.lizhiweike.com/lecture2/29364131 C大调第一把位音阶非常重要,可以多练习&#

游戏视频录制软件推荐,打造专业电竞视频(3款)

随着游戏产业的快速发展&#xff0c;越来越多的玩家开始关注游戏视频录制软件。一款好的录制软件不仅可以帮助玩家记录游戏中的精彩瞬间&#xff0c;还可以让其与他人分享自己的游戏体验。接下来&#xff0c;我们将介绍三款热门的游戏视频录制软件&#xff0c;并对其进行详细的…

【Git】05 分离头指针

文章目录 一、分离头指针二、创建分支三、比较commit内容四、总结 一、分离头指针 正常情况下&#xff0c;在通过git checkout命令切换分支时&#xff0c;在命令后面跟着的是分支名&#xff08;例如master、temp等&#xff09;或分支名对应commit的哈希值。 非正常情况下&…

【网工】华为设备命令学习(nat网络地址转换)

本次实验通过nat技术实现私网转公网。 实验中 pc1和ar2的基本配置省略&#xff0c;只需要配置基本IP地址就行。主要记录AR3的配置代码。 <Huawei>sy Enter system view, return user view with CtrlZ. [Huawei]int g0/0/0 [Huawei-Giga…

在PyTorch中,如何查看深度学习模型的每一层结构?

这里写目录标题 1. 使用print(model)2. 使用torchsummary库3.其余方法&#xff08;可以参考&#xff09; 在PyTorch中&#xff0c;如果想查看深度学习模型的每一层结构&#xff0c;可以使用print(model)或者model.summary()&#xff08;如果你使用的是torchsummary库&#xff0…

第2节、让电机转起来【51单片机+L298N步进电机系列教程】

↑↑↑点击上方【目录】&#xff0c;查看本系列全部文章 摘要&#xff1a;本节介绍用简单的方式&#xff0c;让步进电机转起来。其目的之一是对电机转动有直观的感受&#xff0c;二是熟悉整个开发流程。本系列教程必要的51单片机基础包括IO口操作、中断、定时器三个部分&#…

多模态对比语言图像预训练CLIP:打破语言与视觉的界限,具备零样本能力

多模态对比语言图像预训练CLIP:打破语言与视觉的界限,具备零样本能力。 一种基于多模态(图像、文本)对比训练的神经网络。它可以在给定图像的情况下,使用自然语言来预测最相关的文本片段,而无需为特定任务进行优化。CLIP的设计类似于GPT-2和GPT-3,具备出色的零射击能力…

MATLAB知识点:逻辑运算函数

​讲解视频&#xff1a;可以在bilibili搜索《MATLAB教程新手入门篇——数学建模清风主讲》。​ MATLAB教程新手入门篇&#xff08;数学建模清风主讲&#xff0c;适合零基础同学观看&#xff09;_哔哩哔哩_bilibili 节选自第3章 3.4.4 逻辑运算 3.4.4.1 逻辑运算函数 在上…

springboo冬奥会科普平台源码和论文

随着信息技术和网络技术的飞速发展&#xff0c;人类已进入全新信息化时代&#xff0c;传统管理技术已无法高效&#xff0c;便捷地管理信息。为了迎合时代需求&#xff0c;优化管理效率&#xff0c;各种各样的管理平台应运而生&#xff0c;各行各业相继进入信息管理时代&#xf…