本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderC - Shortest Mountain Climbing Route【题目描述】Takahashi enjoys mountain climbing and is planning a traverse route through a mountain range. The mountain range hasN NNpoints arranged in a line, numbered from1 11toN NN, and the elevation of each pointi ii(1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N) isA i A_iAimeters.Takahashi chooses a pair of integers( l , r ) (l, r)(l,r)satisfying1 ≤ l ≤ r ≤ N 1 \leq l \leq r \leq N1≤l≤r≤N, and walks a route that passes through each point in order from pointl llto pointr rrin ascending order of their numbers. The number of points included in this route isr − l 1 r - l 1r−l1.Thetotal elevation changeof this route is defined as the sum of the absolute differences in elevation between adjacent points along the route, namely:∑ i l r − 1 ∣ A i 1 − A i ∣ \sum_{il}^{r-1} |A_{i1} - A_i|∑ilr−1∣Ai1−Ai∣Note that whenl r l rlr, this sum is an empty sum, so the total elevation change is0 00.Takahashi wants to walk a route with a total elevation change of at leastK KKfor training purposes. However, since he is short on time, he wants to choose a route that satisfies the condition while containing the fewest number of points.If a route with a total elevation change of at leastK KKexists, find the minimum number of points included in such a route. If no such route exists, output− 1 -1−1.高桥热爱登山正在规划一条穿越山脉的路线。这座山脉有N NN个点排成一行编号从1 11到N NN每个点i ii1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N的海拔高度为A i A_iAi米。高桥选择一对满足1 ≤ l ≤ r ≤ N 1 \leq l \leq r \leq N1≤l≤r≤N的整数( l , r ) (l, r)(l,r)并按编号递增的顺序依次经过从点l ll到点r rr的每个点。这条路线包含的点的数量为r − l 1 r - l 1r−l1。这条路线的总海拔变化定义为沿线相邻点之间海拔差的绝对值之和即∑ i l r − 1 ∣ A i 1 − A i ∣ \sum_{il}^{r-1} |A_{i1} - A_i|∑ilr−1∣Ai1−Ai∣注意当l r l rlr时这是一个空和因此总海拔变化为0 00。高桥为了训练目的想要走一条总海拔变化至少为K KK的路线。但是由于时间有限他想在满足条件的前提下选择包含最少点的路线。如果存在总海拔变化至少为K KK的路线求此类路线中包含的最小点数。如果不存在这样的路线输出− 1 -1−1。【输入】N NNK KKA 1 A_1A1A 2 A_2A2… \ldots…A N A_NANThe first line contains an integerN NNrepresenting the number of points and an integerK KKrepresenting the lower bound on the total elevation change, separated by a space.The second line contains integersA 1 , A 2 , … , A N A_1, A_2, \ldots, A_NA1,A2,…,ANrepresenting the elevation of each point, separated by spaces.【输出】If a route with a total elevation change of at leastK KKexists, output the minimum number of points included in such a route on a single line. If no such route exists, output− 1 -1−1.【输入样例】5 5 1 4 2 5 3【输出样例】3【算法标签】#双指针【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN200005;// 定义最大数组长度intn,k;// 数组长度n目标和kinta[N],sa[N];// 数组a前缀和数组sa此处未使用signedmain()// 主函数{cinnk;// 输入数组长度和目标和for(inti1;in;i)// 读取数组元素cina[i];// 输入第i个元素// for (int i2; in; i) // 计算相邻元素差的前缀和被注释掉// sa[i] sa[i-1] abs(a[i]-a[i-1]);intsum0;// 当前窗口内相邻元素差的绝对值之和intansn1;// 初始化答案为n1表示未找到for(intl1,r1;rn;r)// 滑动窗口l为左指针r为右指针{if(rl)// 如果窗口内有多个元素sumabs(a[r]-a[r-1]);// 将新增的相邻差加入总和while(lrsumk)// 当总和超过或等于k时尝试缩小窗口{ansmin(ans,r-l1);// 更新最小窗口长度sum-abs(a[l1]-a[l]);// 移除左边界相邻差l;// 左指针右移}}if(ansn1)cout-1endl;// 如果未找到满足条件的窗口输出-1elsecoutansendl;// 否则输出最小窗口长度return0;// 程序正常结束}【运行结果】5 5 1 4 2 5 3 3
题解：AtCoder AT_awc0087_c Shortest Mountain Climbing Route
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderC - Shortest Mountain Climbing Route【题目描述】Takahashi enjoys mountain climbing and is planning a traverse route through a mountain range. The mountain range hasN NNpoints arranged in a line, numbered from1 11toN NN, and the elevation of each pointi ii(1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N) isA i A_iAimeters.Takahashi chooses a pair of integers( l , r ) (l, r)(l,r)satisfying1 ≤ l ≤ r ≤ N 1 \leq l \leq r \leq N1≤l≤r≤N, and walks a route that passes through each point in order from pointl llto pointr rrin ascending order of their numbers. The number of points included in this route isr − l 1 r - l 1r−l1.Thetotal elevation changeof this route is defined as the sum of the absolute differences in elevation between adjacent points along the route, namely:∑ i l r − 1 ∣ A i 1 − A i ∣ \sum_{il}^{r-1} |A_{i1} - A_i|∑ilr−1∣Ai1−Ai∣Note that whenl r l rlr, this sum is an empty sum, so the total elevation change is0 00.Takahashi wants to walk a route with a total elevation change of at leastK KKfor training purposes. However, since he is short on time, he wants to choose a route that satisfies the condition while containing the fewest number of points.If a route with a total elevation change of at leastK KKexists, find the minimum number of points included in such a route. If no such route exists, output− 1 -1−1.高桥热爱登山正在规划一条穿越山脉的路线。这座山脉有N NN个点排成一行编号从1 11到N NN每个点i ii1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N的海拔高度为A i A_iAi米。高桥选择一对满足1 ≤ l ≤ r ≤ N 1 \leq l \leq r \leq N1≤l≤r≤N的整数( l , r ) (l, r)(l,r)并按编号递增的顺序依次经过从点l ll到点r rr的每个点。这条路线包含的点的数量为r − l 1 r - l 1r−l1。这条路线的总海拔变化定义为沿线相邻点之间海拔差的绝对值之和即∑ i l r − 1 ∣ A i 1 − A i ∣ \sum_{il}^{r-1} |A_{i1} - A_i|∑ilr−1∣Ai1−Ai∣注意当l r l rlr时这是一个空和因此总海拔变化为0 00。高桥为了训练目的想要走一条总海拔变化至少为K KK的路线。但是由于时间有限他想在满足条件的前提下选择包含最少点的路线。如果存在总海拔变化至少为K KK的路线求此类路线中包含的最小点数。如果不存在这样的路线输出− 1 -1−1。【输入】N NNK KKA 1 A_1A1A 2 A_2A2… \ldots…A N A_NANThe first line contains an integerN NNrepresenting the number of points and an integerK KKrepresenting the lower bound on the total elevation change, separated by a space.The second line contains integersA 1 , A 2 , … , A N A_1, A_2, \ldots, A_NA1,A2,…,ANrepresenting the elevation of each point, separated by spaces.【输出】If a route with a total elevation change of at leastK KKexists, output the minimum number of points included in such a route on a single line. If no such route exists, output− 1 -1−1.【输入样例】5 5 1 4 2 5 3【输出样例】3【算法标签】#双指针【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN200005;// 定义最大数组长度intn,k;// 数组长度n目标和kinta[N],sa[N];// 数组a前缀和数组sa此处未使用signedmain()// 主函数{cinnk;// 输入数组长度和目标和for(inti1;in;i)// 读取数组元素cina[i];// 输入第i个元素// for (int i2; in; i) // 计算相邻元素差的前缀和被注释掉// sa[i] sa[i-1] abs(a[i]-a[i-1]);intsum0;// 当前窗口内相邻元素差的绝对值之和intansn1;// 初始化答案为n1表示未找到for(intl1,r1;rn;r)// 滑动窗口l为左指针r为右指针{if(rl)// 如果窗口内有多个元素sumabs(a[r]-a[r-1]);// 将新增的相邻差加入总和while(lrsumk)// 当总和超过或等于k时尝试缩小窗口{ansmin(ans,r-l1);// 更新最小窗口长度sum-abs(a[l1]-a[l]);// 移除左边界相邻差l;// 左指针右移}}if(ansn1)cout-1endl;// 如果未找到满足条件的窗口输出-1elsecoutansendl;// 否则输出最小窗口长度return0;// 程序正常结束}【运行结果】5 5 1 4 2 5 3 3
