算法竞赛备考冲刺必刷题（C++） | 洛谷 P1638 逛画展

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P1714 切蛋糕 - 洛谷

【题目描述】

今天是小 Z 的生日，同学们为他带来了一块蛋糕。这块蛋糕是一个长方体，被用不同色彩分成了n nn个相同的小块，每小块都有对应的幸运值。

小 Z 作为寿星，自然希望吃到的蛋糕的幸运值总和最大，但小 Z 最多又只能吃m ( m ≤ n ) m(m\le n)m(m≤n)小块的蛋糕。

请你帮他从这n nn小块中找出连续的k ( 1 ≤ k ≤ m ) k(1 \le k\le m)k(1≤k≤m)块蛋糕，使得其上的总幸运值最大。

形式化地，在数列{ p n } \{p_n\}{pn​}中，找出一个子段[ l , r ] ( r − l + 1 ≤ m ) [l,r](r-l+1\le m)[l,r](r−l+1≤m)，最大化∑ i = l r p i \sum\limits_{i=l}^rp_ii=l∑r​pi​。

【输入】

第一行两个整数n , m n,mn,m。分别代表共有n nn小块蛋糕，小 Z 最多只能吃m mm小块。

第二行n nn个整数，第i ii个整数p i p_ipi​代表第i ii小块蛋糕的幸运值。

【输出】

仅一行一个整数，即小 Z 能够得到的最大幸运值。

【输入样例】

5 2 1 2 3 4 5

【输出样例】

9

【算法标签】

《洛谷 P1714 切蛋糕》 #单调队列# #前缀和# #队列# ST表

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将int重新定义为long long类型constintN=500005;// 定义常量N，最大数组大小intn,m,a[N],sa[N],ans=-1e9;// n: 数组长度, m: 最大子数组长度, a: 原始数组, sa: 前缀和数组, ans: 结果structNode{ints,idx;// s: 前缀和值, idx: 索引位置};deque<Node>dq;// 双端队列，用于维护滑动窗口最小值signedmain()// 因为使用了#define int long long, 所以用signed main{cin>>n>>m;// 输入数组长度和最大子数组长度for(inti=1;i<=n;i++){cin>>a[i];// 输入数组元素sa[i]=sa[i-1]+a[i];// 计算前缀和}for(inti=1;i<=n;i++){// 维护队列：删除超出窗口范围的元素// 窗口大小为m，只考虑i-m到i-1的前缀和while(dq.size()){if(dq.front().idx<i-m)// 如果队首元素索引小于i-m，超出窗口范围dq.pop_front();// 删除队首元素elsebreak;// 否则停止}// 维护队列：保持队列单调递增// 如果队尾元素的前缀和大于等于当前前缀和，则删除队尾元素// 因为对于后面的i来说，当前元素更优（前缀和更小，索引更靠后）while(dq.size()){if(dq.back().s>=sa[i-1])// 如果队尾元素的前缀和大于等于当前前缀和dq.pop_back();// 删除队尾元素elsebreak;// 否则停止}// 将当前元素的前缀和加入队列dq.push_back({sa[i-1],i-1});// 更新答案：当前前缀和减去队列最小值// 即sa[i] - sa[j] 表示子数组a[j+1...i]的和ans=max(ans,sa[i]-dq.front().s);}cout<<ans<<endl;// 输出最大子数组和return0;}

【运行结果】

5 2 1 2 3 4 5 9