文章目录
1、数的范围
2、数的三次方根
3、前缀和
4、子矩阵的和
5、机器人跳跃问题
1、数的范围
题目
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。对于每个查询，返回一个元素 k的起始位置和终止位置（位置从 00 开始计数）。如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。第二行包含 n 个整数（均在 1∼100001∼10000 范围内），表示完整数组。接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。如果数组中不存在该元素，则返回 -1 -1。
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
b=int(input())
l,r=0,n-1
while l<r:
zz=(l+r)//2
if b<=a[zz]:
r=zz
else: l=zz+1
if a[l]==b:
print(l,end=' ')
else :
print(-1,end=' ')
l,r=0,n-1
while l<r:
zz=(l+r+1)>>1
if b>=a[zz]:
l=zz
else: r=zz-1
if a[l]==b:
print(l)
else:print(-1)
2、数的三次方根
题目
给定一个浮点数 n，求它的三次方根。
输入格式
共一行，包含一个浮点数 n。
输出格式
共一行，包含一个浮点数，表示问题的解。注意，结果保留 66 位小数。
l,r=-10000,10000
n=float(input())
while r>l+10**-8:
mid=(l+r)/2
if mid**3<=n:
l=mid
else: r=mid
print("%.6f"%r)3、前缀和
题目
输入一个长度为 n 的整数序列。接下来再输入 m 个询问，每个询问输入一对 l,r。对于每个询问，输出原序列中从第 l个数到第 r 个数的和。
输入格式
第一行包含两个整数 n和 m。第二行包含 n 个整数，表示整数数列。接下来 m行，每行包含两个整数 l 和 r，表示一个询问的区间范围。
输出格式
共 m行，每行输出一个询问的结果。
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(1,n):
a[i]+=a[i-1]
while m:
l,r=map(int,input().split())
if l==1:
print(a[r-1])
else:print(a[r-1]-a[l-2])
m-=14、子矩阵的和
题目
输入一个 n行 m列的整数矩阵，再输入 q个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n，m，q。接下来 n行，每行包含 m 个整数，表示整数矩阵。接下来 q行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。
输出格式
共 q行，每行输出一个询问的结果。文章来源：https://www.toymoban.com/news/detail-861256.html
n,m,q=map(int,input().split())
mt=[[0 for _ in range(m+1)]for __ in range(n+1)]
sm=[[0 for _ in range(m+1)]for __ in range(n+1)]
for i in range(1,n+1):
mt[i][1:]=list(map(int,input().split()))
sm[0][0]=mt[0][0]
for i in range(1,n+1):
for j in range(1,m+1):
sm[i][j]=sm[i][j-1]+sm[i-1][j]+mt[i][j]-sm[i-1][j-1]
for i in range(q):
x1,y1,x2,y2=map(int,input().split())
print(sm[x2][y2]-sm[x2][y1-1]-sm[x1-1][y2]+sm[x1-1][y1-1])
5、机器人跳跃问题
题目
机器人正在玩一个古老的基于 DOS 的游戏。游戏中有 N+1 座建筑——从 00 到 N编号，从左到右排列。编号为 00 的建筑高度为 00 个单位，编号为 i的建筑高度为 H(i)个单位。起初，机器人在编号为 00 的建筑处。每一步，它跳到下一个（右边）建筑。假设机器人在第 k个建筑，且它现在的能量值是 E，下一步它将跳到第 k+1个建筑。如果 H(k+1)>E，那么机器人就失去 H(k+1)−E 的能量值，否则它将得到 E−H(k+1)的能量值。游戏目标是到达第 N个建筑，在这个过程中能量值不能为负数个单位。现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？
输入格式
第一行输入整数 N。第二行是 N个空格分隔的整数，H(1),H(2),…,H(N)代表建筑物的高度。
输出格式
输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。文章来源地址https://www.toymoban.com/news/detail-861256.html
n = int(input())
#l,r = 0,10**5+10
h = list(map(int,input().split()))
l,r = 0,max(h)
def check(x):
for i in range(n):
x+= x - h[i]
if x < 0:
return False
return True
while l < r:
mid = l + r >> 1
if check(mid):
r = mid
else:
l = mid + 1
print(l)
到了这里，关于【二分与前缀和】python例题详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
