题解：洛谷 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

【核心思想】

1. 问题分析：给定n nn位小朋友，第i ii位至少需要a i a_iai​颗糖果，且每位小朋友分得的糖果必须严格多于前一位。求最少需要准备的总糖果数。这是一个贪心策略问题，核心在于在满足单调递增约束的前提下，让每个小朋友分得尽可能少的糖果。

2. 算法选择：

   • 贪心构造：从左到右遍历，每位小朋友的糖果数取a i a_iai​和s i − 1 + 1 s_{i-1} + 1si−1​+1的最大值，确保既满足最低需求又满足严格递增

3. 关键步骤：

   • 读入数据：读取n nn和数组a [ 1.. n ] a[1..n]a[1..n]
   • 贪心构造（i ii从1 11到n nn）：
     • s 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_{i=1}^{n} s_ians←∑i=1n​si​
   • 输出结果：a n s ansans

4. 时间/空间复杂度：

   • 时间复杂度：O ( n ) O(n)O(n)，单次线性遍历
   • 空间复杂度：O ( n ) O(n)O(n)，存储s ss数组（可优化为O ( 1 ) O(1)O(1)滚动变量）

5. 贪心策略的核心思想：

   • 局部最优保证全局最优：对于第i ii位小朋友，在满足所有约束条件下取最小值，即max ⁡ ( a i , s i − 1 + 1 ) \max(a_i, s_{i-1} + 1)max(ai​,si−1​+1)。这个局部最优选择不会影响后续的选择（因为后续只需满足> s i > s_i>si​），因此贪心策略正确
   • 单调递增的最低成本：严格递增序列的最低成本构造方式是每次只比前一位多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)空间
   • 适用于带约束的单调序列构造、最小成本满足条件类贪心问题

【算法标签】

#普及- #贪心

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 定义int为long long类型constintN=1005;// 定义数组最大长度intn;// 输入的数字个数inta[N];// 存储原始数字数组ints[N];// 存储处理后的数字数组intans=0;// 存储最终结果signedmain(){// 输入数字个数cin>>n;// 输入n个数字for(inti=1;i<=n;i++)cin>>a[i];// 处理数组，确保s[i]至少比前一个大1for(inti=1;i<=n;i++)s[i]=max(a[i],s[i-1]+1);// 计算处理后数组的总和for(inti=1;i<=n;i++){ans+=s[i];}// 输出最终结果cout<<ans<<endl;return0;}

【运行结果】

4 1 4 3 3 16