PAT乙级_1120 买地攻略_Python_AC解法_含疑难点
注意事项：
因为笔者的编程水平以自学为主，代码结构可能比较混乱、变量命名可能不够规范。
文章中的AC解法不一定最优，并且包含笔者强烈的个人风格，不喜勿喷，但欢迎在评论中理性讨论或者给出提升建议。
文章中提到的疑难点仅为个人在刷题过程中所遇到的情况，如有读者存在其他疑难点，欢迎在评论中加以补充，笔者会尽量将其加入到文章内容中。
合集：
PAT乙级_合集_Python_AC解法
题目：
1120 买地攻略
题目描述：
数码城市有土地出售。待售的土地被划分成若干块，每一块标有一个价格。这里假设每块土地只有两块相邻的土地，除了开头和结尾的两块是只有一块邻居的。每位客户可以购买多块连续相邻的土地。
现给定这一系列土地的标价，请你编写程序，根据客户手头的现金量，告诉客户有多少种不同的购买方案。
输入格式：
输入首先在第一行给出两个正整数：N（≤10^4）为土地分割的块数（于是这些块从 1 到 N 顺次编号）；M（≤10^9）为客户手中的现金量。
随后一行给出 N 个正整数，其中第 i 个数字就是第 i 块土地的标价。
题目保证所有土地的总价不超过 10^9。
输出格式：
在一行中输出客户有多少种不同的购买方案。请注意客户只能购买连续相邻的土地。
输入样例：
5 85
38 42 15 24 9
输出样例：
11
样例解释：
这 11 种不同的方案为：
38
42
15
24
9
38 42
42 15
42 15 24
15 24
15 24 9
24 9
代码限制：
代码长度限制
16 KB
时间限制
150 ms
内存限制
64 MB
栈限制
8192 KB
AC解法：
# 获取输入数据
n, m = map(int, input().split()) # 切分土地数和预算上限
lands = list(map(int, input().split())) # 获取各个土地的单价# 处理数据并输出结果
price = [0] * (n + 1) # 创建初始值全为 0 的空列表用于前缀和计算，长度为 n+1
for i in range(1, n + 1): # 遍历下标，范围为 [1, n]price[i] = price[i - 1] + lands[i - 1] # 计算前缀和值
cnt = 0 # 初始化计数值为 0
right = 1 # 创建右指针，初始值为 1
for left in range(n): # 遍历左指针范围while right <= n and price[right] - price[left] <= m: # 只要右指针未超过上限，# 且左指针起至当前右指针位置的连续土地总价没有超过预算上限right += 1 # 右指针继续右移，即 +1cnt += (right - left - 1) # 当不满足 while 循环时，计数加上当前左右指针表示的可能数# 对于左指针 left ，满足条件的右指针位置是 left+1 至 right-1，实际数量即 (right-1)-(left+1)+1
print(cnt) # 输出购买方案数量
题目解读：
本题描述比较易懂。
先获取输入的数据，再依次判断各个数量连续的土地总价是否低于预算上限并进行计数，最后输出计数结果。
疑难点：
测试点2、测试点3、测试点6、测试点7运行超时
若直接使用双重循环遍历土地的同时频繁使用 sum 求和计算总价是否超过预算，就会导致这四个测试点都超时。
如果仅采用前缀和（若不太了解前缀和，可参考文章：＜蓝桥杯软件赛＞零基础备赛20周--第9周--前缀和与差分_以下是一段求前缀和的并行程序代码-CSDN博客）优化总价的计算，只能多通过一个测试点3。
要想通过剩余三个测试点，则需要采用双指针替换双重循环。