【二分与前缀和】python例题详解

文章目录

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-=1

4、子矩阵的和

题目
输入一个 n行 m列的整数矩阵，再输入 q个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n，m，q。接下来 n行，每行包含 m 个整数，表示整数矩阵。接下来 q行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。
输出格式
共 q行，每行输出一个询问的结果。

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)代表建筑物的高度。
输出格式
输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。

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)