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

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个小朋友坐成一圈&#xff0c;每人有 a[i]个糖果。 每人只能给左右两人传递糖果。 每人每次传递一个糖果代价为 1。 求使所有人获得均等糖果的最小代价。 输入格式 第一行输入一个正整数 n&#xff0c;表示小朋友的个数。 接下来 n 行&#xff0c;每行一个整数 a[i]&…...

Redis中的单线程模型

文章目录 文件事件处理器模型Redis的客户端与服务端的交互过程图Redis基于Reactor模式开发了自己的网络事件处理器,称之为 文件事件处理器(File Event Hanlder)。 文件事件处理器由Socket、IO多路复用程序文件事件分派器(dispather)事件处理器(handler)文件事件处理器模型 IO…...

Python函数默认参数设置(超级详细)

我们知道&#xff0c;在调用函数时如果不指定某个参数&#xff0c;Python 解释器会抛出异常。为了解决这个问题&#xff0c;Python 允许为参数设置默认值&#xff0c;即在定义函数时&#xff0c;直接给形式参数指定一个默认值。这样的话&#xff0c;即便调用函数时没有给拥有默…...

人工智能如何赋能业务创新?安克创新有话要说

对于一家企业来说&#xff0c;应该如何运用人工智能技术助力业务创新&#xff1f;作为一家多年复合增长率超过35%的企业&#xff0c;安克创新对这个话题无疑有着深切的体验感悟。飞速成长的消费电子企业众所周知&#xff0c;当下各行各业都在如火如荼地开展人工智能应用&#x…...

如何学习与学习的本质

如何学习两种模式两种记忆方式拖延问题学习方法学习本质两种模式 专注模式发散模式 专注模式和发散模式可以进行切换&#xff0c;提高效率&#xff0c; 发散模式可以后台工作。 两种记忆方式 工作记忆&#xff08;前额叶皮质&#xff09;长时记忆&#xff08;图像比较容易记…...

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文档学习&#xff08;四&#xff09; 文章目录编写你的第一个 Django 应用&#xff0c;第 6 部分自定义应用的界面和风格编写你的第一个 Django 应用&#xff0c;第 7 部分自定义后台表单自定义后台更改列表自定义后台界面和风格自定义后台主页编写你的第一…...

2023年全国最新高校辅导员精选真题及答案38

百分百题库提供高校辅导员考试试题、辅导员考试预测题、高校辅导员考试真题、辅导员证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 112.为改变重知识传授轻能力培养的大学课堂&#xff0c;教学方法可以采用&#xff08;&am…...

和ChatGPT-4聊完后,我觉得一切可能已经来不及了

了然无味&#xff0c;晴空万里&#xff01;和ChatGPT-4开始了一场坦诚的沟通&#xff0c;它全程都表现出高情商&#xff0c;以及不断尽量安抚我的情绪&#xff0c;而这&#xff0c;恰恰令我脊背发凉。 部分文字截取 ZM&#xff1a;我能不能理解每次对话就是一次你的“生命” G&…...

RocketMQ 5.1 NameServer 启动流程

文章目录1 解析命令行参数和配置文件2 创建并启动 NamesrvController2.1 创建 NamesrvController 对象2.2 启动 NamesrvController 对象第一步&#xff1a;初始化 controller第二步&#xff1a;注册 JVM 钩子第二步&#xff1a;启动 controllerRocketMQ是一个分布式消息中间件&…...

马云回国,首谈ChatGPT

马云今天回国了&#xff0c;这是一个备受关注的消息。 作为中国最具代表性的企业家之一&#xff0c;马云在过去的二十多年里&#xff0c;带领阿里巴巴从一个小小的创业公司&#xff0c;发展成为全球最大的电商平台之一&#xff0c;同时也推动了中国互联网行业的发展。 他的回…...

深入理解C++迭代器:让你的C++代码更加灵活

C迭代器&#xff1a;更加优雅的容器操作方式引言C迭代器简介a. 迭代器的定义b. 迭代器的作用c. 迭代器与指针的区别迭代器分类a. 输入迭代器&#xff08;Input Iterator&#xff09;b. 输出迭代器&#xff08;Output Iterator&#xff09;c. 前向迭代器&#xff08;Forward Ite…...

Java 读取Excel模板中的数据到实体类

目录一. 前提条件1.1 需求1.2 分析二. 准备2.1 自定义注解2.2 封装Excel的实体类三. 前台四. Controller层五. Service层&#x1f4aa;&#x1f4aa;&#x1f4aa;六. 效果一. 前提条件 1.1 需求 从指定的Excel模板中读取数据&#xff0c;将读取到的数据存储到数据库中。 1.2…...

【java基础】Socket网络编程

文章目录说明InetAddress介绍Socket介绍ServerSocket介绍实现简单的Socket通信总结说明 这里介绍下如何在java里面进行socket编程 InetAddress介绍 这个类表示一个Internet协议(IP)地址&#xff0c;我们可以通过ip或者主机名来构建这个类 Testpublic void t1() throws Except…...

转发和重定向区别

转发和重定向 1.0 面试提问 定义不同跳转的方式不同数据共享不同最终的URL地址不同代码实现不同 1. 转发 1.1 概念 转发实际上在服务器端进行页面的跳转操作&#xff0c;请求转发&#xff1a;一种在服务器内部的资源的跳转的方式。 访问A&#xff0c;A请求转发了B&#xff0c…...

java面试题(持续更新)

java面试题&#xff08;持续更新&#xff09; java 基础 java面向对象有哪些特征 面向对象的三大特征&#xff1a;封装、继承、多态 封装&#xff1a;隐藏了类的内部实现机制&#xff0c;可以在不影响使用的情况下改变类的内部结构&#xff0c;同时也保护了数据&#xff0c;…...

【花雕学AI】09:发挥ChatGPT最大潜力——产生高质量内容的九种方法和建议

人工智能&#xff08;AI&#xff09;是当今科技领域最热门和最有前景的话题之一&#xff0c;它已经渗透到了我们生活和工作的方方面面&#xff0c;给我们带来了许多便利和惊喜。而在AI的众多分支中&#xff0c;自然语言处理&#xff08;NLP&#xff09;是最贴近人类的一个领域&…...

实战打靶集锦-013-Loly

**写在前面&#xff1a;**记录博主的一次打靶经历 目录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学习法

版权声明 本文原创作者&#xff1a;谷哥的小弟作者博客地址&#xff1a;http://blog.csdn.net/lfdfhl OKR管理法 OKR&#xff08;Objectives and Key Results&#xff09;管理法是一种目标管理方法&#xff0c;旨在通过制定明确的目标和可量化的关键结果来帮助组织、团队和个人…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

MyBatis中关于缓存的理解

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

GraphRAG优化新思路-开源的ROGRAG框架

目前的如微软开源的GraphRAG的工作流程都较为复杂&#xff0c;难以孤立地评估各个组件的贡献&#xff0c;传统的检索方法在处理复杂推理任务时可能不够有效&#xff0c;特别是在需要理解实体间关系或多跳知识的情况下。先说结论&#xff0c;看完后感觉这个框架性能上不会比Grap…...