当瓦莱拉有空闲时间时他会去图书馆看书。今天他有t分钟的空闲时间。所以瓦莱拉从图书馆拿了n本书并且为每本书估算了阅读所需的时间。我们用数字 1 到n给这些书编号。瓦莱拉需要a[i]分钟来读第i本书。瓦莱拉决定从编号为i的书开始依次阅读书籍。也就是说他先读第i本书然后是第i 1 本接着是第i 2 本依此类推。他会一直读直到时间用完或者读完第n本书。瓦莱拉不会半途而废——如果时间不够读完一本书他就不会开始读它。请你输出瓦莱拉最多能读多少本书。输入格式第一行包含两个整数n和t(1 ≤n≤ 10^5; 1 ≤t≤ 10^9) —— 书的数量和瓦莱拉的空闲分钟数。第二行包含n个整数a1,a2, ...,an(1 ≤a[i]≤ 10^4)其中第a[i]个数表示瓦莱拉读第i本书所需的分钟数。输出格式输出一个整数——瓦莱拉最多能读多少本书。样例InputOutput4 5 3 1 2 13InputOutput3 3 2 2 31一、 题目分析题目大意 你有空闲时间t分钟有n本书排成一排每本书阅读需要a[i]分钟。你只能挑连续的一段书阅读问最多能读几本核心洞察 题目隐含了一个极其重要的物理常识阅读时间a[i]必定都是正数。 这意味着你读的书越多花的时间一定越长严格单调递增。这就完美契合了“滑动窗口”和“双指针”的使用场景我们可以像拉尺子一样贪心地往右吃进新书如果时间超标了就从左边吐出旧书。二、 思考过程与代码演进针对这个物理模型我们来看看三种不同的实现思路。阶段一队列模拟滑动窗口很多同学的第一反应是用一个队列把读过的书存起来超时了就让队首出队。设计思路 维护一个队列数组q不断把新书的下标压入队尾并累加时间sum。如果sum超过了允许的t就用一个while循环不断把队首的书弹出去直到时间恢复合法。//codeforces-279B //第一种做法 队列滑动窗口 #include iostream #include algorithm//对应min max using namespace std; int a[100010];//存储每本书阅读时间 int q[100010];//队列存图书下标 int front1,rear0;//队首 队尾 int n,t; int sum;//存储当前队列中所有书阅读总时间 int ma;//最多能读多少本书 int main(){ //n本书 空闲分钟数 cinnt; //每本书阅读时间 for(int i1;in;i) cina[i]; for(int i1;in;i){ //把当前第i本书入队 q[rear]i; //同时更新总时间和最多能读多少本书 suma[i];//更新总时间 //如果阅读了当前这本书 加上队列中所有书阅读时间 //即当前总时间sum不超过t 就更新最多能读多少本书 if(sumt){ //更新最多可以读多少书 mamax(ma,rear-front1); } //如果阅读了当前这本书 加上队列中所有书阅读时间 //即当前总时间sum超过t else{ //就把当前队首的书出队 直到不超过t while(sumt){ //更新总时间(减掉队首所需时间 sum-a[q[front]]; //队首的书出队 front; } } } coutma; return 0; }点评这版代码物理意义极其明确不过单独开一个数组q来做队列空间上略显浪费。阶段二原地双指针标答既然每次吐掉的都是窗口最左边的书我们真的需要一个额外的队列数组来记录吗不需要直接用一个左指针跟着跑就行了。设计思路 省去队列数组只用一个变量l代表窗口左边界随着for循环里的i右边界一起向右滑。吃撑了就sum-a[l]并且l极其干净利落。//codeforces-279B //第二种做法 双指针滑动窗口 #include iostream #include algorithm//对应min max using namespace std; int a[100010];//存储每本书阅读时间 int n,t; int sum;//存储当前队列中所有书阅读总时间 int ma;//最多能读多少本书 int main(){ //n本书 空闲分钟数 cinnt; //每本书阅读时间 for(int i1;in;i) cina[i]; int l1;//左指针 从第一本书开始 for(int i1;in;i){//右指针 //当阅读第i本书 更新总时间 suma[i]; while(sumt){//如果阅读了这本书 总时间超过t sum-a[l];//吐出来最左边的书 l;//左端点右移 } //只要满足时间小于等于t 就计算一次最大值 mamax(ma,i-l1); } coutma; return 0; }点评这是这道题最完美的标答。没有任何多余的数组核心逻辑只有短短四五行空间复杂度被压缩到了O(1)。在考场上这种无脑把结算放在循环最末尾的写法容错率高不会漏掉边界。阶段三前缀和 双指针这是一种纯粹的数学降维思维。把“维护一个动态的框”转换成了“在静态的前缀和数组上找差值”。设计思路 预处理出所有书的前缀和s。然后左边界i从1到n遍历右边界r只要满足s[r]-s[i-1]t就无脑往右推进。//codeforces-279B //第三种做法 双指针前缀和 #include iostream #include algorithm//对应min max using namespace std; int a[100010];//存储每本书阅读时间 int s[100010];//前缀和 int n,t; int ma;//最多能读多少本书 int main(){ //n本书 空闲分钟数 cinnt; //每本书阅读时间 for(int i1;in;i) cina[i]; //求这n本书的前缀和 for(int i1;in;i) s[i]a[i]s[i-1]; int r1;//连续区间右端点位置 for(int i1;in;i){ //只要在时间范围内右端点就不断往右摸索 while(rns[r]-s[i-1]t) r; //退出循环时r刚好停在“第一本读不完的书”上 mamax(ma,r-i); } coutma; return 0; }点评这版代码的精妙之处在于右指针r定义在主循环外面利用前缀和的单调性r永远不会往回走。且当while循环被打断时r-i算出来的刚好就是这一轮能合法读完的本数连1或-1的边界补丁都不需要打数学逻辑严丝合缝。三、 时空复杂度分析与易错点总结时空复杂度时间复杂度这三种方法都是O(N)。不管是双指针的移动还是队列的进出每个元素最多被访问或操作两次。空间复杂度方法二仅需存储原数组省去了额外结构方法一和三需要额外O(N)的辅助数组。易错点总结防范数据溢出风险虽然本题t最大只有10^9累加的sum在出队机制的保护下最多只比t大一点点不会超过int的极限。但在其他区间求和类题目中如果数据量达到10^5级别把累加器sum开成long long永远是安全的好习惯。
Books（Codeforces- P279B）
发布时间：2026/5/25 15:22:51
当瓦莱拉有空闲时间时他会去图书馆看书。今天他有t分钟的空闲时间。所以瓦莱拉从图书馆拿了n本书并且为每本书估算了阅读所需的时间。我们用数字 1 到n给这些书编号。瓦莱拉需要a[i]分钟来读第i本书。瓦莱拉决定从编号为i的书开始依次阅读书籍。也就是说他先读第i本书然后是第i 1 本接着是第i 2 本依此类推。他会一直读直到时间用完或者读完第n本书。瓦莱拉不会半途而废——如果时间不够读完一本书他就不会开始读它。请你输出瓦莱拉最多能读多少本书。输入格式第一行包含两个整数n和t(1 ≤n≤ 10^5; 1 ≤t≤ 10^9) —— 书的数量和瓦莱拉的空闲分钟数。第二行包含n个整数a1,a2, ...,an(1 ≤a[i]≤ 10^4)其中第a[i]个数表示瓦莱拉读第i本书所需的分钟数。输出格式输出一个整数——瓦莱拉最多能读多少本书。样例InputOutput4 5 3 1 2 13InputOutput3 3 2 2 31一、 题目分析题目大意 你有空闲时间t分钟有n本书排成一排每本书阅读需要a[i]分钟。你只能挑连续的一段书阅读问最多能读几本核心洞察 题目隐含了一个极其重要的物理常识阅读时间a[i]必定都是正数。 这意味着你读的书越多花的时间一定越长严格单调递增。这就完美契合了“滑动窗口”和“双指针”的使用场景我们可以像拉尺子一样贪心地往右吃进新书如果时间超标了就从左边吐出旧书。二、 思考过程与代码演进针对这个物理模型我们来看看三种不同的实现思路。阶段一队列模拟滑动窗口很多同学的第一反应是用一个队列把读过的书存起来超时了就让队首出队。设计思路 维护一个队列数组q不断把新书的下标压入队尾并累加时间sum。如果sum超过了允许的t就用一个while循环不断把队首的书弹出去直到时间恢复合法。//codeforces-279B //第一种做法 队列滑动窗口 #include iostream #include algorithm//对应min max using namespace std; int a[100010];//存储每本书阅读时间 int q[100010];//队列存图书下标 int front1,rear0;//队首 队尾 int n,t; int sum;//存储当前队列中所有书阅读总时间 int ma;//最多能读多少本书 int main(){ //n本书 空闲分钟数 cinnt; //每本书阅读时间 for(int i1;in;i) cina[i]; for(int i1;in;i){ //把当前第i本书入队 q[rear]i; //同时更新总时间和最多能读多少本书 suma[i];//更新总时间 //如果阅读了当前这本书 加上队列中所有书阅读时间 //即当前总时间sum不超过t 就更新最多能读多少本书 if(sumt){ //更新最多可以读多少书 mamax(ma,rear-front1); } //如果阅读了当前这本书 加上队列中所有书阅读时间 //即当前总时间sum超过t else{ //就把当前队首的书出队 直到不超过t while(sumt){ //更新总时间(减掉队首所需时间 sum-a[q[front]]; //队首的书出队 front; } } } coutma; return 0; }点评这版代码物理意义极其明确不过单独开一个数组q来做队列空间上略显浪费。阶段二原地双指针标答既然每次吐掉的都是窗口最左边的书我们真的需要一个额外的队列数组来记录吗不需要直接用一个左指针跟着跑就行了。设计思路 省去队列数组只用一个变量l代表窗口左边界随着for循环里的i右边界一起向右滑。吃撑了就sum-a[l]并且l极其干净利落。//codeforces-279B //第二种做法 双指针滑动窗口 #include iostream #include algorithm//对应min max using namespace std; int a[100010];//存储每本书阅读时间 int n,t; int sum;//存储当前队列中所有书阅读总时间 int ma;//最多能读多少本书 int main(){ //n本书 空闲分钟数 cinnt; //每本书阅读时间 for(int i1;in;i) cina[i]; int l1;//左指针 从第一本书开始 for(int i1;in;i){//右指针 //当阅读第i本书 更新总时间 suma[i]; while(sumt){//如果阅读了这本书 总时间超过t sum-a[l];//吐出来最左边的书 l;//左端点右移 } //只要满足时间小于等于t 就计算一次最大值 mamax(ma,i-l1); } coutma; return 0; }点评这是这道题最完美的标答。没有任何多余的数组核心逻辑只有短短四五行空间复杂度被压缩到了O(1)。在考场上这种无脑把结算放在循环最末尾的写法容错率高不会漏掉边界。阶段三前缀和 双指针这是一种纯粹的数学降维思维。把“维护一个动态的框”转换成了“在静态的前缀和数组上找差值”。设计思路 预处理出所有书的前缀和s。然后左边界i从1到n遍历右边界r只要满足s[r]-s[i-1]t就无脑往右推进。//codeforces-279B //第三种做法 双指针前缀和 #include iostream #include algorithm//对应min max using namespace std; int a[100010];//存储每本书阅读时间 int s[100010];//前缀和 int n,t; int ma;//最多能读多少本书 int main(){ //n本书 空闲分钟数 cinnt; //每本书阅读时间 for(int i1;in;i) cina[i]; //求这n本书的前缀和 for(int i1;in;i) s[i]a[i]s[i-1]; int r1;//连续区间右端点位置 for(int i1;in;i){ //只要在时间范围内右端点就不断往右摸索 while(rns[r]-s[i-1]t) r; //退出循环时r刚好停在“第一本读不完的书”上 mamax(ma,r-i); } coutma; return 0; }点评这版代码的精妙之处在于右指针r定义在主循环外面利用前缀和的单调性r永远不会往回走。且当while循环被打断时r-i算出来的刚好就是这一轮能合法读完的本数连1或-1的边界补丁都不需要打数学逻辑严丝合缝。三、 时空复杂度分析与易错点总结时空复杂度时间复杂度这三种方法都是O(N)。不管是双指针的移动还是队列的进出每个元素最多被访问或操作两次。空间复杂度方法二仅需存储原数组省去了额外结构方法一和三需要额外O(N)的辅助数组。易错点总结防范数据溢出风险虽然本题t最大只有10^9累加的sum在出队机制的保护下最多只比t大一点点不会超过int的极限。但在其他区间求和类题目中如果数据量达到10^5级别把累加器sum开成long long永远是安全的好习惯。
