欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年青铜组真题解析 | 汇总-CSDN博客
【题目来源】
洛谷：[P9974 USACO23DEC] Candy Cane Feast B - 洛谷
【题目描述】
农夫约翰(FJ)的奶牛非常喜欢吃甜食，尤其喜欢吃拐杖糖！FJ共有N头奶牛，每头奶牛都有一定的初始身高，他想喂养它们M MM根拐杖糖，每根拐杖糖也有不同的高度**( 1 ≤ N , M ≤ 2 ⋅ 10 5 ) (1\le N,M\le 2\cdot 10^5)(1≤N,M≤2⋅105)**。
FJ计划按照输入给出的顺序，一根接一根地把拐杖糖喂给奶牛。为了给他的奶牛喂食拐杖糖，他会把拐杖糖悬挂起来，让拐杖糖的底部刚好碰到地面。然后，奶牛们会按输入给出的顺序一个接一个地排队，走向拐杖糖，每只奶牛都会把自己高度所及的部分的拐杖糖吃掉（因为它们无法触及更高的部分）。即使在奶牛吃掉了底部的拐杖糖之后, 拐杖糖会仍然悬挂在最初竖立的地方，并不会下降到地面上。如果拐杖糖的底部已经高于某只奶牛的身高, 那么这只奶牛可能在轮到她时什么也不吃。在每头奶牛都吃了一次之后，奶牛的身高会随着它们吃了多少单位的拐杖糖而增长，并且农夫约翰会挂上下一根拐杖糖(底部仍然刚好碰到地面), 奶牛们再次重复此过程（1 11号奶牛再次第一个开始吃下一根拐杖糖）。
【输入】
第一行包含N NN和M MM。
第二行包含N NN头奶牛的初始身高，每个身高都在**[ 1 , 10 9 ] [1,10^9][1,109]**的范围内。
第三行包含M MM根拐杖糖的高度，每个高度都在**[ 1 , 10 9 ] [1,10^9][1,109]**的范围内。
【输出】
一共N NN行，每行一个数字，表示N NN头奶牛的最终身高。
【输入样例】
3 2 3 2 5 6 1【输出样例】
7 2 7【算法标签】
《洛谷 P9974 Candy Cane Feast》 #模拟# #USACO# #O2优化# #2023#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;intn,m;ll a[200005];structnode{inttop,bottom;}b[200005];intmain(){cin>>n>>m;// 输入n和mfor(inti=1;i<=n;i++){// 输入n个奶牛的身高cin>>a[i];}for(inti=1;i<=m;i++){// 输入m个拐杖糖的高度cin>>b[i].top;// 输入拐杖糖的高度b[i].bottom=0;// 同时记录该拐杖糖的底部为0}for(inti=1;i<=m;i++){// 先遍历m再遍历n（反过来会超时，部分测试点会TLE）for(intj=1;j<=n;j++){if(b[i].top==0)break;// 如果该拐杖糖已经被吃掉了，则跳过该糖（就是通过该行代码减少了时间复杂度）if(a[j]<=b[i].bottom)continue;// 如果奶牛高度小于糖的底部高度，则说明没法吃到，继续循环if(a[j]>=b[i].bottom&&a[j]<b[i].top){// 如果奶牛高度在糖的高度中间inttmp=a[j];// 记录奶牛高度a[j]=a[j]+(a[j]-b[i].bottom);// 奶牛高度增加吃掉的糖的高度b[i].bottom=tmp;// 将糖的底部高度更新为奶牛的高度}elseif(a[j]>=b[i].top){// 如果奶牛比糖的top位置还高a[j]=a[j]+(b[i].top-b[i].bottom);// 则奶牛高度增加糖的长度（top-bottom）b[i].top=0;// 将糖的top修改为0，即被吃掉}}}for(inti=1;i<=n;i++){// 输出所有奶牛高度cout<<a[i]<<endl;}return0;}【运行结果】
3 2 3 2 5 6 1 7 2 7
