本文分享的必刷题目是从蓝桥云课、洛谷、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 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=1nsi
- 输出结果：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_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
