当前位置: 首页 > 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;旨在通过制定明确的目标和可量化的关键结果来帮助组织、团队和个人…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

如何配置一个sql server使得其它用户可以通过excel odbc获取数据

要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据&#xff0c;你需要完成以下配置步骤&#xff1a; ✅ 一、在 SQL Server 端配置&#xff08;服务器设置&#xff09; 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到&#xff1a;SQL Server 网络配…...

xmind转换为markdown

文章目录 解锁思维导图新姿势&#xff1a;将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件&#xff08;ZIP处理&#xff09;2.解析JSON数据结构3&#xff1a;递归转换树形结构4&#xff1a;Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...