“前缀和 + 全局偏移量 + 二分查找” 预处理 --＞ 求解”最大子序列和“题型

B3799 [NICA #1] 序列 - 洛谷

初始代码无法AC：

        原因存在多次遍历的情况容易超时

import sysdef add_k(nums, k):for w in range(len(nums)):nums[w] += kreturn numsdef max_subsequence_sum(nums):if not nums:return Falsesum_ = sum(i for i in nums if i > 0)if sum_ > 0:return sum_else:return max(nums)def select_operation(nums,operations):res = []for op in operations:if len(op) > 1:add_k(nums,op[1])else:max_subsequence_sum(nums)res.append(max_subsequence_sum(nums))# 删除 --> nums[:] = original # 不用于nums = original 前者实际修改里面的内容，后者修改引用return resn,m = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))
operations = list(tuple(map(int, sys.stdin.readline().split())) for _ in range(m))
print("\n".join(map(str, select_operation(nums,operations))))

优化代码：

import sys
from itertools import accumulatedef main():data = sys.stdin.read().split()iter_ = iter(data)  # 输入数据转换为迭代器n = int(next(iter_))m = int(next(iter_))# 读取原始数组arr = [int(next(iter_))for _ in range(n)]arr.sort(reversed = True)pre = [0] + list(accumulate(arr)) # 预处理数组为”前缀和数组“# 写[0] --- 表示当前求解最大子序列和,可以取空集k_count = 0 # 全局偏移变量kans = [] # 存放输出答案# 在允许操作数内进行操作for _ in range(m):op = int(next(iter_))if op == 1:k = int(next(iter_))k_count += kelif op == 2:left, right = 0, n # 注意边界 6种组合while left < right: mid = left + (right - left) // 2if arr[mid] + k_count > 0:left = mid  # mid位置满足条件，[0 ~ (mid-1)]也一定可以满足,继续向后找，令序列尽可能长else: right = mid - 1    count = left # 索引 = 满足条件的数量, 补充了一个空集[0]的位置if count > 0: # 满足条件的数量至少为1个sum_ = pre[count] + k_count*countelse: # 全为负数，不取任何元素 --- 空集sum_ = 0ans.append(str(sum_))sys.stdout.write("\n".join(ans))if __name__ == "__main__":main()