本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderB - Defense of the Flower Bed【题目描述】高橋正在种植一排N NN盆盆栽植物。它们从左到右编号为1 , 2 , … , N 1, 2, \ldots, N1,2,…,N植物i ii目前含有A i A_iAi​毫升水。由于夏季炎热每天所有盆栽植物的水都会蒸发。具体来说每过一天每盆植物中的水量减少D DD毫升但水量不会降到0 00以下最低为0 00。与此同时淘气的青木正计划破坏高橋的花坛。青木可以在每天开始时最多执行一次操作他可以选择任意一盆植物将其水量设为0 00一种倒掉水的恶作剧。青木总共最多可以执行K KK次这样的操作。他可以选择同一盆植物多次。青木的恶作剧在该天的蒸发发生之前执行。高橋无法补充水也无法阻止蒸发或青木的恶作剧。他希望M MM天后所有M MM天的蒸发和青木的恶作剧都完成后剩余水量至少为1 11毫升的盆栽植物数量尽可能多。青木会采取最优策略使高橋面临最糟糕的结果。换句话说青木选择恶作剧的目标以最小化M MM天后剩余水量至少为1 11毫升的盆栽植物数量。假设青木采取最优策略求M MM天后剩余水量至少为1 11毫升的盆栽植物数量。【输入】N NNM MMD DDK KKA 1 A_1A1​A 2 A_2A2​… \ldots…A N A_NAN​The first line contains the number of potted plantsN NN, the number of daysM MM, the daily evaporation amountD DD, and the maximum number of Aoki’s pranksK KK, separated by spaces.The second line contains the initial water amounts of the potted plantsA 1 , A 2 , … , A N A_1, A_2, \ldots, A_NA1​,A2​,…,AN​, separated by spaces.【输出】Print the number of potted plants with at least1 11milliliter of water remaining afterM MMdays, assuming Aoki acts optimally, in a single line.【输入样例】5 3 2 1 1 5 6 7 10【输出样例】1【核心思想】问题分析给定N NN盆植物初始水量A i A_iAi​每天蒸发D DD毫升不低于 0青木在每天蒸发前最多恶作剧一次将某盆水置 0总共最多K KK次。M MM天后求剩余水量≥ 1 \geq 1≥1的植物最大数量青木采取最优策略最小化该数量。算法选择分类讨论 贪心将植物分为两类——仅靠蒸发就会干枯的A i ≤ M ⋅ D A_i \leq M \cdot DAi​≤M⋅D和蒸发后仍有剩余的A i M ⋅ D A_i M \cdot DAi​M⋅D青木最优策略优先消灭蒸发后仍有剩余的植物这些植物不消灭就会存活每次恶作剧消灭一盆关键步骤读入与排序读入N , M , D , K N, M, D, KN,M,D,K和数组A [ 1.. N ] A[1..N]A[1..N]将A AA从小到大排序统计蒸发干枯数遍历排序后的数组统计满足A i ≤ M ⋅ D A_i \leq M \cdot DAi​≤M⋅D的数量a n s ansans这些植物无需青木干预修正恶作剧次数K min ⁡ ( K , M ) K \min(K, M)Kmin(K,M)青木每天最多一次总次数不超过天数M MM计算存活数蒸发后仍有剩余的植物数为N − a n s N - ansN−ans青木最多消灭min ⁡ ( K , N − a n s ) \min(K, N - ans)min(K,N−ans)盆最终存活数为max ⁡ ( 0 , N − a n s − K ) \max(0, N - ans - K)max(0,N−ans−K)时间/空间复杂度时间复杂度O ( N log ⁡ N ) O(N \log N)O(NlogN)排序主导统计过程O ( N ) O(N)O(N)空间复杂度O ( N ) O(N)O(N)存储水量数组贪心策略的核心思想自然淘汰与人为干预分离A i ≤ M ⋅ D A_i \leq M \cdot DAi​≤M⋅D的植物必然干枯青木无需浪费恶作剧次数优先打击幸存者青木的最优策略是集中力量消灭那些仅靠蒸发无法消灭的植物每消灭一盆直接减少一个存活者次数上限约束恶作剧次数受K KK和M MM双重限制取min ⁡ ( K , M ) \min(K, M)min(K,M)为实际可用次数排序便于分界排序后A i ≤ M ⋅ D A_i \leq M \cdot DAi​≤M⋅D的植物集中在数组前端一次遍历即可统计适用于资源有限的最优打击类问题核心在于识别无需干预的自然死亡目标【算法标签】#贪心【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 将int定义为long long避免水量计算溢出constintN1000005;// 定义数组最大容量为1000005intn,m,d,k,ans;// n为盆栽数量m为天数d为每天蒸发量k为青木最多恶作剧次数ans记录特定统计值inta[N];// a[i]表示第i盆植物的初始水量signedmain()// 使用signed main配合#define int long long{cinnmdk;// 读入盆栽数n、天数m、蒸发量d、恶作剧次数kfor(inti1;in;i)// 读入每盆植物的初始水量cina[i];sort(a1,an1);// 将初始水量从小到大排序// 统计经过M天蒸发后不考虑青木恶作剧水量会降到0的植物数量// 每天蒸发DM天共蒸发M*D如果a[i] M*D则蒸发后水量为0或更低for(inti1;in;i){if(a[i]m*d)// 如果初始水量不超过M天总蒸发量ans;// 该植物仅靠蒸发就会干枯水量变为0}// 青木每天最多恶作剧一次总共最多K次// 但恶作剧天数不能超过总天数M所以实际最多min(K, M)次kmin(k,m);// 修正k为实际可用的恶作剧次数// 核心逻辑// ans仅靠蒸发就会干枯的植物数量这些植物不需要青木操心// n - ans仅靠蒸发不会干枯的植物数量a[i] M*D这些植物需要青木恶作剧才能消灭// 青木最多可以消灭k盆植物每次恶作剧将一盆植物水量设为0// 最终存活数 总植物数 - 蒸发干枯数 - 青木消灭数// n - ans - min(k, n - ans)// max(0, n - ans - k)coutmax(0LL,n-ans-k)endl;// 输出M天后剩余水量至少为1毫升的盆栽数量return0;}【运行结果】5 3 2 1 1 5 6 7 10 1