本题可以翻译为:给定一个数组,求数组区间和大于等于m的最小值,并把区间和等于该最小值的区间找出来
两层for循环暴力枚举所有区间,然后计算前缀和
n,m = map(int,input().split())
a = [0] * (n + 10)
s = [0] * (n + 10)
for i,x in enumerate(map(int,input().split()),start = 1):
a[i] = x
s[i] = s[i - 1] + a[i]
res = float('inf')
for i in range(1,n + 1):
for j in range(1,i + 1):
if s[i] - s[j - 1] >= m:
res = min(res,s[i] - s[j - 1]) # 记录顾客需要支付的最小金额
for i in range(1,n + 1):
for j in range(1,i + 1):
if s[i] - s[j - 1] == res:
print(f'{j}-{i}')
双指针算法:
枚举区间时先枚举区间的右端点i
,对于每个i
找到一个==最靠右==(注意因为是最靠右的左端点,所以写代码时应该采用预判法)的左端点j
使得从j
到i
的区间和是大于等于m
的,
因为j
越靠右,这意味着j
~i
之间的总和越小。对于每个i
都找出这样的j
(虽然有的i
可能找不到这样的j
),计算j
到i
的区间和res,并对这些全部的res取min,最终的res就是需要支付的金额
因为所有的数都是大于0的,可以证明j
一定是不会往左走的,即i
往右走,其对应的j
要么不走,要么往右走,因此可以使用双指针
n,m = map(int,input().split())
a = [0] * (n + 10)
s = [0] * (n + 10)
for i,x in enumerate(map(int,input().split()),start = 1):
a[i] = x
s[i] = s[i - 1] + a[i]
res = float('inf')
j = 1
for i in range(1,n + 1):
# 如果j往后走(提前预判),s[i] - s[j + 1 - 1]仍然大于等于m,那么j ++。
while j + 1 <= i and s[i] - s[j] >= m:
j += 1
"""
注意,这个if判断必须要有
如果对于这个i,上面的while循环进去过一次,那么这个if语句确实不用写,对于这个i,s[i] - s[j - 1]肯定大于m
但是对于这个i,上面的while循环可能都没进去过,那么s[i] - s[j - 1]是否>= m是不确定的
因为不是每个i都有与之对应定义的j
"""
if s[i] - s[j - 1] >= m:
res = min(res,s[i] - s[j - 1])
j = 1
for i in range(1,n + 1):
while j + 1 <= i and s[i] - s[j] >= m:
j += 1
if s[i] - s[j - 1] == res:
print(f'{j}-{i}')
另一种双指针的枚举方法:
枚举区间时先枚举区间的左端点i
,对于每个i
找到一个==最靠左==(注意因为是最靠左(重点字在这,而不是左右端点)的右端点,所以写代码时应该采用==条件相反法==,条件是大于等于m,则在while循环写小于m)的右端点j
使得从i
到j
的区间和是大于等于m
的,
因为j
越靠左,这意味着i
~j
之间的总和越小。对于每个i
都找出这样的j
(虽然有的i
可能找不到这样的j
),计算i
到j
的区间和res,并对这些全部的res取min,最终的res就是需要支付的金额
因为所有的数都是大于0的,可以证明j
一定是不会往左走的,即i
往右走,其对应的j
要么不走,要么往右走,因此可以使用双指针
n,m = map(int,input().split())
a = [0] * (n + 10)
s = [0] * (n + 10)
for i,x in enumerate(map(int,input().split()),start = 1):
a[i] = x
s[i] = s[i - 1] + a[i]
res = float('inf')
j = 1
for i in range(1,n + 1):
while j <= n and s[j] - s[i - 1] < m: # 条件相反法
j += 1
# 因为不是对于每个i都有与之对应的定义的j,所以要有这个if判断
if s[j] - s[i - 1] >= m:
res = min(res,s[j] - s[i - 1])
j = 1
for i in range(1,n + 1):
while j <= n and s[j] - s[i - 1] < m:
j += 1
if s[j] - s[i - 1] == res:
print(f'{i}-{j}')