旅游团
GESP C++ 5级模拟题
题目名称：旅游团
知识点
- 循环结构（for循环、嵌套循环）
- 条件判断（if语句）
- 数学运算（加法、比较）
- 算法思维（滑动窗口思想）
题目描述
小明计划参加一个旅游团，但他只有 t 天假期，不够完成整个旅游行程。贴心的旅行社老板允许他中途加入旅游团，跟随旅游团游览一段时间。
这个旅游团有 n 个景点，按顺序游览。旅行社计划用 a_i 天游览第 i 个景点。
小明可以从这 n 个景点中的任意一个开始加入旅游团。一旦加入，他必须按照旅游团的顺序，一个接一个地游览后续景点。如果发现自己的假期不够去下一个景点（比如只剩1天，但下一个景点需要2天），他就会选择在当前景点结束行程。
请计算小明最多能游览多少个景点。
输入格式
第一行，包含两个整数 n 和 t，分别表示景点数量和小明的假期天数
（1 ≤ n ≤ 50000，1 ≤ t ≤ 10^9）
第二行，包含 n 个正整数 a₁, a₂, ..., aₙ，表示游览第 i 个景点所需的天数
（1 ≤ a_i ≤ 1000）
输出格式
一行，输出一个整数，表示小明最多能游览的景点数量。
样例输入1
4 5
3 1 2 1
样例输出1
3
样例1说明：
- 景点1需要3天，景点2需要1天，景点3需要2天，景点4需要1天
- 如果从景点1开始：3天（景点1）+ 1天（景点2）+ 2天（景点3）= 6天 > 5天，只能游览景点1和景点2，共2个景点
- 如果从景点2开始：1天（景点2）+ 2天（景点3）+ 1天（景点4）= 4天 ≤ 5天，可以游览景点2、3、4，共3个景点
- 如果从景点3开始：2天（景点3）+ 1天（景点4）= 3天 ≤ 5天，可以游览景点3、4，共2个景点
- 如果从景点4开始：1天（景点4），可以游览景点4，共1个景点
- 最多能游览3个景点
样例输入2
5 10
2 3 4 1 5
样例输出2
4
样例2说明：
- 从景点2开始：3 + 4 + 1 + 5 = 13天 > 10天
- 从景点2开始：3 + 4 + 1 = 8天 ≤ 10天，可以游览景点2、3、4，共3个景点
- 从景点3开始：4 + 1 + 5 = 10天 ≤ 10天，可以游览景点3、4、5，共3个景点
- 从景点1开始：2 + 3 + 4 + 1 = 10天 ≤ 10天，可以游览景点1、2、3、4，共4个景点
- 最多能游览4个景点
样例输入3
3 2
5 1 1
样例输出3
2
样例3说明：
- 从景点1开始：5天 > 2天，无法游览
- 从景点2开始：1 + 1 = 2天 ≤ 2天，可以游览景点2、3，共2个景点
- 从景点3开始：1天 ≤ 2天，可以游览景点3，共1个景点
- 最多能游览2个景点
提示
-
算法思路：
- 枚举所有可能的起点（从第1个到第n个景点）
- 对于每个起点，尽可能多地游览后续景点
- 记录所有起点中能游览的最多景点数
-
实现步骤：
- 外层循环：枚举起点 i（从0到n-1）
- 内层循环：从起点i开始，累加景点天数，直到总天数超过t
- 更新最大景点数
-
注意事项：
- 如果从某个景点开始，该景点本身的天数就超过t，则无法游览任何景点
- 需要找到所有起点中，能游览最多景点的方案
-
时间复杂度：
- 最坏情况 O(n²)，对于n≤50000可能较慢
- 可以使用滑动窗口优化到O(n)
难度评估
难度： ⭐⭐⭐⭐☆（中等偏难）
适合： GESP C++ 一级考生练习
算法思维考察点
- 枚举思想：需要枚举所有可能的起点
- 贪心思想：从每个起点开始，尽可能多地游览景点
- 滑动窗口：可以使用滑动窗口优化时间复杂度
- 边界处理：需要正确处理无法游览任何景点的情况