AcWing——糖果传递
有 n个小朋友坐成一圈,每人有 a[i]个糖果。
每人只能给左右两人传递糖果。
每人每次传递一个糖果代价为 1。
求使所有人获得均等糖果的最小代价。
输入格式
第一行输入一个正整数 n,表示小朋友的个数。
接下来 n 行,每行一个整数 a[i],表示第 i个小朋友初始得到的糖果的颗数。
输出格式
输出一个整数,表示最小代价。
数据范围
1≤n≤1000000
0≤a[i]≤2×109
数据保证一定有解。
输入样例:
4
1
2
5
4
输出样例:
4
题意:
ai向ai+1传递xi个通过(xi可正可负),求abs(x1)+abs(x2)+...+abs(xn)的最小值
分析:
一大堆数学证明我证不过来,所以直接给结论吧。
要求
|x1|+|x2|+...+|xn|最小值,
即求
|xn-b-a1|+|xn-2b-a1-a2|+|xn-nb-a1-a2-...-an|
将该问题转换为
货仓选址问题即可
#include <iostream>
#include <algorithm>using namespace std;
typedef long long ll;
const int N=1e6+10;
ll a[N],b,c[N];
int main(){int n;cin>>n;for(int i=1;i<=n;++i){cin>>a[i];b+=a[i];a[i]+=a[i-1];}b/=n;for(int i=1;i<=n;++i){c[i]=i*b-a[i];}sort(c+1,c+n+1);ll d=c[n/2+1];ll res=0;for(int i=1;i<=n;++i){res+=abs(c[i]-d);}cout<<res;return 0;
}
相关文章:
AcWing——糖果传递
有 n个小朋友坐成一圈,每人有 a[i]个糖果。 每人只能给左右两人传递糖果。 每人每次传递一个糖果代价为 1。 求使所有人获得均等糖果的最小代价。 输入格式 第一行输入一个正整数 n,表示小朋友的个数。 接下来 n 行,每行一个整数 a[i]&…...
Redis中的单线程模型
文章目录 文件事件处理器模型Redis的客户端与服务端的交互过程图Redis基于Reactor模式开发了自己的网络事件处理器,称之为 文件事件处理器(File Event Hanlder)。 文件事件处理器由Socket、IO多路复用程序文件事件分派器(dispather)事件处理器(handler)文件事件处理器模型 IO…...
Python函数默认参数设置(超级详细)
我们知道,在调用函数时如果不指定某个参数,Python 解释器会抛出异常。为了解决这个问题,Python 允许为参数设置默认值,即在定义函数时,直接给形式参数指定一个默认值。这样的话,即便调用函数时没有给拥有默…...
人工智能如何赋能业务创新?安克创新有话要说
对于一家企业来说,应该如何运用人工智能技术助力业务创新?作为一家多年复合增长率超过35%的企业,安克创新对这个话题无疑有着深切的体验感悟。飞速成长的消费电子企业众所周知,当下各行各业都在如火如荼地开展人工智能应用&#x…...
如何学习与学习的本质
如何学习两种模式两种记忆方式拖延问题学习方法学习本质两种模式 专注模式发散模式 专注模式和发散模式可以进行切换,提高效率, 发散模式可以后台工作。 两种记忆方式 工作记忆(前额叶皮质)长时记忆(图像比较容易记…...
C++ deque容器
C deque容器 文章目录C deque容器前言1. deque容器基本概念2. deque构造函数3. deque赋值操作4. deque大小操作5. deque 插入和删除6. deque 数据存取7. deque 排序总结前言 本文包含deque容器基本概念、deque构造函数、deque赋值操作、deque大小操作、deque插入和删除、deque…...
HashMap的底层原理
hashmap是一个以key,value形式存储的集合,在JDK1.7中是以数组链表的数据结构,在JDK1.8中是数组链表红黑树的数据结构,他在对数据操作时继承了数组的线性查找和链表的寻址修改 hashmap是线程不安全的 : 在JDK1.7中会造成环形链和数据丢失的情况 在JDK1.8中hashmap的put过程会造…...
Django 4.0文档学习(四)
上篇文章 Django 4.0文档学习(四) 文章目录编写你的第一个 Django 应用,第 6 部分自定义应用的界面和风格编写你的第一个 Django 应用,第 7 部分自定义后台表单自定义后台更改列表自定义后台界面和风格自定义后台主页编写你的第一…...
2023年全国最新高校辅导员精选真题及答案38
百分百题库提供高校辅导员考试试题、辅导员考试预测题、高校辅导员考试真题、辅导员证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。 112.为改变重知识传授轻能力培养的大学课堂,教学方法可以采用(&am…...
和ChatGPT-4聊完后,我觉得一切可能已经来不及了
了然无味,晴空万里!和ChatGPT-4开始了一场坦诚的沟通,它全程都表现出高情商,以及不断尽量安抚我的情绪,而这,恰恰令我脊背发凉。 部分文字截取 ZM:我能不能理解每次对话就是一次你的“生命” G&…...
RocketMQ 5.1 NameServer 启动流程
文章目录1 解析命令行参数和配置文件2 创建并启动 NamesrvController2.1 创建 NamesrvController 对象2.2 启动 NamesrvController 对象第一步:初始化 controller第二步:注册 JVM 钩子第二步:启动 controllerRocketMQ是一个分布式消息中间件&…...
马云回国,首谈ChatGPT
马云今天回国了,这是一个备受关注的消息。 作为中国最具代表性的企业家之一,马云在过去的二十多年里,带领阿里巴巴从一个小小的创业公司,发展成为全球最大的电商平台之一,同时也推动了中国互联网行业的发展。 他的回…...
深入理解C++迭代器:让你的C++代码更加灵活
C迭代器:更加优雅的容器操作方式引言C迭代器简介a. 迭代器的定义b. 迭代器的作用c. 迭代器与指针的区别迭代器分类a. 输入迭代器(Input Iterator)b. 输出迭代器(Output Iterator)c. 前向迭代器(Forward Ite…...
Java 读取Excel模板中的数据到实体类
目录一. 前提条件1.1 需求1.2 分析二. 准备2.1 自定义注解2.2 封装Excel的实体类三. 前台四. Controller层五. Service层💪💪💪六. 效果一. 前提条件 1.1 需求 从指定的Excel模板中读取数据,将读取到的数据存储到数据库中。 1.2…...
【java基础】Socket网络编程
文章目录说明InetAddress介绍Socket介绍ServerSocket介绍实现简单的Socket通信总结说明 这里介绍下如何在java里面进行socket编程 InetAddress介绍 这个类表示一个Internet协议(IP)地址,我们可以通过ip或者主机名来构建这个类 Testpublic void t1() throws Except…...
转发和重定向区别
转发和重定向 1.0 面试提问 定义不同跳转的方式不同数据共享不同最终的URL地址不同代码实现不同 1. 转发 1.1 概念 转发实际上在服务器端进行页面的跳转操作,请求转发:一种在服务器内部的资源的跳转的方式。 访问A,A请求转发了B,…...
java面试题(持续更新)
java面试题(持续更新) java 基础 java面向对象有哪些特征 面向对象的三大特征:封装、继承、多态 封装:隐藏了类的内部实现机制,可以在不影响使用的情况下改变类的内部结构,同时也保护了数据,…...
【花雕学AI】09:发挥ChatGPT最大潜力——产生高质量内容的九种方法和建议
人工智能(AI)是当今科技领域最热门和最有前景的话题之一,它已经渗透到了我们生活和工作的方方面面,给我们带来了许多便利和惊喜。而在AI的众多分支中,自然语言处理(NLP)是最贴近人类的一个领域&…...
实战打靶集锦-013-Loly
**写在前面:**记录博主的一次打靶经历 目录1. 主机发现2. 端口扫描3. 服务枚举4. web服务探查4.1 WordPress探测4.2 使用metasploit4.3 使用wpscan4.4 阶段性回顾5. 提权5.1 弱密码提权5.2 操作系统信息枚举5.3 定时任务枚举5.4 passwd信息枚举5.5 可执行文件枚举5.…...
程序员OKR学习法
版权声明 本文原创作者:谷哥的小弟作者博客地址:http://blog.csdn.net/lfdfhl OKR管理法 OKR(Objectives and Key Results)管理法是一种目标管理方法,旨在通过制定明确的目标和可量化的关键结果来帮助组织、团队和个人…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
