题解：洛谷 B4359 [GESP202506 三级] 分糖果

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷B4359 [GESP202506 三级] 分糖果 - 洛谷【题目描述】有n nn位小朋友排成一队等待老师分糖果。第i ii位小朋友想要至少a i a_iai​颗糖果并且分给他的糖果数量必须比分给前一位小朋友的糖果数量更多不然他就会不开心。老师想知道至少需要准备多少颗糖果才能让所有小朋友都开心。你能帮帮老师吗【输入】第一行一个正整数n nn表示小朋友的人数。第二行n nn个正整数a 1 , a 2 , … , a n a_1,a_2,…,a_na1​,a2​,…,an​依次表示每位小朋友至少需要的糖果数量。【输出】输出一行一个整数表示最少需要准备的糖果数量。【输入样例】4 1 4 3 3【输出样例】16【核心思想】问题分析给定n nn位小朋友第i ii位至少需要a i a_iai​颗糖果且每位小朋友分得的糖果必须严格多于前一位。求最少需要准备的总糖果数。这是一个贪心策略问题核心在于在满足单调递增约束的前提下让每个小朋友分得尽可能少的糖果。算法选择贪心构造从左到右遍历每位小朋友的糖果数取a i a_iai​和s i − 1 1 s_{i-1} 1si−1​1的最大值确保既满足最低需求又满足严格递增关键步骤读入数据读取n nn和数组a [ 1.. n ] a[1..n]a[1..n]贪心构造i ii从1 11到n nns i ← max ⁡ ( a i , s i − 1 1 ) s_i \leftarrow \max(a_i, s_{i-1} 1)si​←max(ai​,si−1​1)解释s i s_isi​至少为a i a_iai​满足最低需求且至少为s i − 1 1 s_{i-1} 1si−1​1满足严格多于前一位累加求和a n s ← ∑ i 1 n s i ans \leftarrow \sum_{i1}^{n} s_ians←∑i1n​si​输出结果a n s ansans时间/空间复杂度时间复杂度O ( n ) O(n)O(n)单次线性遍历空间复杂度O ( n ) O(n)O(n)存储s ss数组可优化为O ( 1 ) O(1)O(1)滚动变量贪心策略的核心思想局部最优保证全局最优对于第i ii位小朋友在满足所有约束条件下取最小值即max ⁡ ( a i , s i − 1 1 ) \max(a_i, s_{i-1} 1)max(ai​,si−1​1)。这个局部最优选择不会影响后续的选择因为后续只需满足 s i s_isi​因此贪心策略正确单调递增的最低成本严格递增序列的最低成本构造方式是每次只比前一位多1 11即s i s i − 1 1 s_i s_{i-1} 1si​si−1​1。但当a i a_iai​更大时必须以a i a_iai​为下限前缀依赖第i ii位的最优解只依赖于前一位的值具有无后效性适合从左到右的贪心处理空间优化实际上只需维护前一个s i − 1 s_{i-1}si−1​的值无需完整数组可优化为O ( 1 ) O(1)O(1)空间适用于带约束的单调序列构造、最小成本满足条件类贪心问题【算法标签】#普及- #贪心【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 定义int为long long类型constintN1005;// 定义数组最大长度intn;// 输入的数字个数inta[N];// 存储原始数字数组ints[N];// 存储处理后的数字数组intans0;// 存储最终结果signedmain(){// 输入数字个数cinn;// 输入n个数字for(inti1;in;i)cina[i];// 处理数组确保s[i]至少比前一个大1for(inti1;in;i)s[i]max(a[i],s[i-1]1);// 计算处理后数组的总和for(inti1;in;i){anss[i];}// 输出最终结果coutansendl;return0;}【运行结果】4 1 4 3 3 16