AcWing 122 糖果传递(贪心)
[题目概述]
有 n 个小朋友坐成一圈,每人有 a[i] 个糖果。
每人只能给左右两人传递糖果。
每人每次传递一个糖果代价为 1。
求使所有人获得均等糖果的最小代价。
输入格式
第一行输入一个正整数 n,表示小朋友的个数。
接下来 n 行,每行一个整数 a[i],表示第 i 个小朋友初始得到的糖果的颗数。
输出格式
输出一个整数,表示最小代价。
数据范围
1 ≤ n ≤ 1000000 , 1 ≤ n ≤ 1000000, 1≤n≤1000000,
0 ≤ a [ i ] ≤ 2 × 1 0 9 0 ≤ a[i] ≤ 2×10^9 0≤a[i]≤2×109
数据保证一定有解。
输入样例:
4
1
2
5
4
输出样例:
4
贪心法感觉就是在解数学题,将题目抽象成一个数学模型,推出来结论就能写,推不出来就废。
我们可以将每次传递的糖果用x数组表示

然后就开始了数学推导



然后我们就将及其复杂的问题化成了一个简单的模型。
- 完整代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int N = 1000010;int a[N], n;
long long c[N];
long long sum, avg, ret;
int main(){cin >> n;for(int i = 1; i <= n; i ++){cin >> a[i];sum += a[i];}avg = sum / n;// 求c数组for(int i = n; i > 1; i --){c[i] = c[i + 1] + avg - a[i];} sort(c + 1, c + n + 1);// 求最小价值for(int i = 1; i <= n; i ++){ret += abs(c[i] - c[(n + 1) / 2]);}cout << ret << endl;return 0;
}
- 本题的分享就结束了,贪心感觉比其他难很多,这就是推出来结论就能做,推不出来就根本不会,上下浮动很大,很难学。
相关文章:
AcWing 122 糖果传递(贪心)
[题目概述] 有 n 个小朋友坐成一圈,每人有 a[i] 个糖果。 每人只能给左右两人传递糖果。 每人每次传递一个糖果代价为 1。 求使所有人获得均等糖果的最小代价。 输入格式 第一行输入一个正整数 n,表示小朋友的个数。 接下来 n 行,每行一个…...
unity的重中之重:组件
检查器(Hierarchy)面板中的所有东西都是组件。日后多数工作都是和组件打交道,包括调参、自定义脚本组件。 文章目录 12 游戏的灵魂,脚本组件13 玩转脚本组件14 尽职的一生,了解组件的生命周期15 不能插队!…...
Linux释放内存
free -m是Linux上查看内存的指令,其中-m是以兆(MB)为单位,如果不加则以KB为单位。 如下图表示,(total)总物理内存是809MB,(used)已使用167MB,&…...
Python算法题集_翻转二叉树
Python算法题集_翻转二叉树 题226:翻转二叉树1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【DFS递归】2) 改进版一【BFS迭代,节点循环】3) 改进版二【BFS迭代,列表循环】 4. 最优算法 本文为Python算法题集…...
Git快速掌握,通俗易懂
Git分布式版本控制工具 介绍 Git是一个开源的分布式版本控制系统,用于敏捷高效地处理任何或小或大的项目。Git是由Linus Torvalds为了帮助管理Linux内核开发而开发的一个开放源码的版本控制软件。Git可以帮助开发者们管理代码的版本,避免代码冲突&#…...
PHP毕业设计图片分享网站76t17
图片分享网站主要是为了提高工作人员的工作效率和更方便快捷的满足用户,更好存储所有数据信息及快速方便的检索功能,对系统的各个模块是通过许多今天的发达系统做出合理的分析来确定考虑用户的可操作性,遵循开发的系统优化的原则,…...
代码随想录 Leetcode45. 跳跃游戏 II
题目: 代码(首刷看解析 2024年2月15日): class Solution { public:int jump(vector<int>& nums) {if (nums.size() 1) return 0;int res 0;int curDistance 0;int nextDistance 0;for (int i 0; i < nums.size(); i) {nex…...
【C语言】socketpair 的系统调用
一、 Linux 内核 4.19socketpair 的系统调用 SYSCALL_DEFINE4(socketpair, int, family, int, type, int, protocol,int __user *, usockvec) {return __sys_socketpair(family, type, protocol, usockvec); } 这段代码定义了一个名为 socketpair 的系统调用。系统调用是操作…...
【论文精读】BERT
摘要 以往的预训练语言表示应用于下游任务时的策略有基于特征和微调两种。其中基于特征的方法如ELMo使用基于上下文的预训练词嵌入拼接特定于任务的架构;基于微调的方法如GPT使用未标记的文本进行预训练,并针对有监督的下游任务进行微调。 但上述两种策略…...
Codeforces Round 925 (Div. 3) - A、B、C、D、E
文章目录 前言A. Recovering a Small StringB. Make EqualC. Make Equal AgainD. Divisible PairsE. Anna and the Valentines Day Gift 前言 本篇博客是Codeforces Round 925周赛的A、B、C、D、E五题的题解 A. Recovering a Small String 可以通过sum的大小分为三种情况&#…...
快速部署MES源码/万界星空科技开源MES
什么是开源MES软件? 开源MES软件是指源代码可以免费获取、修改和分发的MES软件。与传统的商业MES软件相比,开源MES软件具有更高的灵活性和可定制性。企业可以根据自身的需求对软件进行定制化开发,满足不同生产环境下的特定需求。 开源MES软件…...
【Python网络编程之TCP三次握手】
🚀 作者 :“码上有前” 🚀 文章简介 :Python开发技术 🚀 欢迎小伙伴们 点赞👍、收藏⭐、留言💬 Python网络编程之[TCP三次握手] 代码见资源,效果图如下一、实验要求二、协议原理2.…...
【leetcode】深搜、暴搜、回溯、剪枝(C++)2
深搜、暴搜、回溯、剪枝(C)2 一、括号生成1、题目描述2、代码3、解析 二、组合1、题目描述2、代码3、解析 三、目标和1、题目描述2、代码3、解析 四、组合总和1、题目描述2、代码3、解析 五、字母大小写全排列1、题目描述2、代码3、解析 六、优美的排列1…...
鸿蒙开发-UI-图形-图片
鸿蒙开发-UI-组件 鸿蒙开发-UI-组件2 鸿蒙开发-UI-组件3 鸿蒙开发-UI-气泡/菜单 鸿蒙开发-UI-页面路由 鸿蒙开发-UI-组件导航-Navigation 鸿蒙开发-UI-组件导航-Tabs 文章目录 一、基本概念 二、图片资源加载 1. 存档图类型数据源 2.多媒体像素图 三、显示矢量图 四、图片…...
.NET Core WebAPI中使用Log4net记录日志
一、安装NuGet包 二、添加配置 // log4net日志builder.Logging.AddLog4Net("CfgFile/log4net.config");三、配置log4net.config文件 <?xml version"1.0" encoding"utf-8"?> <log4net><!-- Define some output appenders -->…...
Nginx配置php留档
好久没有用过php了,近几日配置nginxphp,留档。 安装 ubunt下nginx和php都可以使用apt安装: sudo apt install nginx php8 如果想安装最新的php8.2,则需要运行下面语句: sudo dpkg -l | grep php | tee packages.txt sudo add-…...
英语题不会怎么搜答案?分享五个支持答案和解析的工具 #学习方法#媒体
在大学的学习过程中,我们常常会遇到一些难以解决的问题,有时候甚至会感到束手无策。然而,如今的技术发展给我们提供了新的解决方案。搜题软件作为一种强大的学习工具,正在被越来越多的大学生所接受和使用。今天,我将为…...
Rust 数据结构与算法:4栈:用栈实现进制转换
2、进展转换 将十进制数转换为二进制表示形式的最简单方法是“除二法”,可用栈来跟踪二进制结果。 除二法 下面实现一个将十进制数转换为二进制或十六进制的算法,代码如下: #[derive(Debug)] struct Stack<T> {size: usize, // 栈大…...
树莓派4B(Raspberry Pi 4B)使用docker搭建阿里巴巴sentinel服务
树莓派4B(Raspberry Pi 4B)使用docker搭建阿里巴巴sentinel服务 由于国内访问不了docker hub,而国内镜像仓库又没有适配树莓派ARM架构的sentinel镜像,所以我们只能退而求其次——自己动手构建镜像。本文基于Ubuntu,Jav…...
Django视图
HttpRequests对象 利用http协议向服务器传参的4种途径 提取url特定部分,如/web/index/,可以通过在服务器端的路由中用正则表达式截取查询字符串,形如?key1value&keyvalue2,(?前面是路由,…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...
20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
Spring Security 认证流程——补充
一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...
6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础
第三周 Day 3 🎯 今日目标 理解类(class)和对象(object)的关系学会定义类的属性、方法和构造函数(init)掌握对象的创建与使用初识封装、继承和多态的基本概念(预告) &a…...
