题目描述
H国最近在和M国打仗，H国间谍头子Peter负责监视敌国M的兵力部署情况。M国沿边境线布置了N个营地，Peter的任务就是监视这些营地的兵力部署情况。中央情报局要研究敌情，所以Peter要汇报一段兵营中哪个连续的K个营地驻兵最少之和是多少，可以作为攻击的突破点，例如：“Peter，快汇报第2个营地到第10个营地中H连续的3座兵营人数之和最少”；而且每个营地的人数在不断变化。请你帮Peter设计一个程序，快速计算汇到的结果
输入描述
第一行3个正整数：N K L
N(N<=50000),表示敌人营地兵营的数量，每个营地编号为1,2,3...N.K表示连续的兵营数,L表示后续要问的命令数量；接下来有N个正整数，第i个正整数ai代表第i个营地里开始时有ai个人（1<=ai<=50000）
接下来有行有L条命令。命令有3种形式：
(1)Add i j, i和j为正整数，表示第i个营地增加j个人（j不超过30）
(2)Sub i j, i和j为正整数，表示第i个营地减少j个人（j不超过30）
(3)Query i j, i和j为正整数, i<=j，表示询问问第i个营地到第j个营地，连续H个兵营人数之和最少的总人数
其中: j-i+1>=K，每组数据最多有50条命令
输出描述
对于每个Query询问，输出一个整数并回车，表示询问的该段中的连续的K座兵营人数之和最少的数量，这个数保持在int以内。
示例1
输入
5 2 3
1 2 2 3 3
Query 1 3
Add 3 6
Query 2 4
输出
3
10
说明
> 说明 第一行第一个正整数5，表示敌人有5个营地，第二个正整数2，表示连续营地 的数量是2， 第3个正整数3，表示后续会有3条询问的命令；接下来一行有 5个正整数，分别表示每个营地里开使的人数，第1个营地开始有1个人，第 2个营地开始有2个人，第3个营地开始有2个人，第4个营地开始有3个人，第5 个营地开始有3个人； > > 接下来每行有一条命令： > > 第1条命令：Query 1 3 表示要查询第1到第3个营地的总人数，结果：1+2=3 第一个输出是：3 > > 第2条命令：Add 3 6 表示第3个营地增加6个人 无需输出 > > 第3条命令：Query 2 4 表示查询第2到第4个营地的总人数，结果： > > 2+8=10 第一个输出是：10，注意这里第3个营地人数在第2条命令中增加了 6
import sys
def input_data():
n,k,l = map(int,sys.stdin.readline().strip().split())
bingying = [0]+ list(map(int, sys.stdin.readline().strip().split()))
command = []
for i in range(l):
command_data = sys.stdin.readline().strip().split()
command_data_order = command_data[0]
command_data_i = int(command_data[1])
command_data_j = int(command_data[2])
command.append((command_data_order, command_data_i, command_data_j))
return command, n,k,l,bingying
def find_min_data(command,k,bingying):
result = []
for order,i,j in command:
if order == 'Query':
min_sum = query_data(bingying,i,j,k)
result.append(str(min_sum))
elif order == 'Add' or order == 'Sub':
add_or_sub(bingying,i,j,order)
else:
raise Exception('命令不对')
return result
def add_or_sub(bingying,i,j,order):
if order == 'Add':
bingying[i]+=j
elif order == 'Sub':
bingying[i]-=j
def query_data(bingying,i,j,k):
left = i
right = i+k
current_sum = sum(bingying[i:i+k])
min_sum = current_sum
while right<=j:
min_sum = min(current_sum + bingying[right] -bingying[left],min_sum)
left+=1
right+=1
return min_sum
def process_min_data():
command, n, k, l, bingying = input_data()
print(command, n, k, l, bingying)
result = find_min_data(command,k,bingying)
return '\n'.join(result)
if __name__ == '__main__':
print(process_min_data())5 2 3
1 2 2 3 3
Query 1 3
Add 3 6
Query 2 4
[('Query', 1, 3), ('Add', 3, 6), ('Query', 2, 4)] 5 2 3 [0, 1, 2, 2, 3, 3]
3
10算法核心思想与步骤总结
问题本质
这是一个动态区间查询与修改问题，需要在支持动态更新的数组中，快速查询指定区间内所有长度为K的连续子数组的最小和。
核心算法思想
1. 滑动窗口法 (Sliding Window)
目的：高效计算连续子数组的和
原理：维护一个固定大小为K的窗口，通过滑动来遍历所有可能的子数组
优势：将时间复杂度从O(N²)降低到O(N)
2. 增量更新策略
当窗口向右滑动时：
移除左边界元素：
current_sum - bingying[left]添加右边界新元素：
+ bingying[right]更新当前和：
current_sum = current_sum - bingying[left] + bingying[right]