蓝桥杯（二）——二分与前缀和

目录

一、二分

二、二分例题

1. 数的范围

2. 分巧克力

三、前缀和

四、前缀和例题

1. 子矩阵的和

---

一、二分

1. 方法一

1. 确定一个区间，使得目标值在一定区间中

2. 找一个性质满足：性质具有二段性；答案是二段性的分界点 

整数二分：

第一类：ans是红色区间的右端点(ans>=x)

将[L,R]分为[L,M-1]和[M,R]

ps:区间不是[L,M]的原因：M正好为红色时无法区分是在[L,M]还是[M+1,R]

if M是红色的，说明ans在区间[M,R]

else 说明ans在区间[L,M-1]

伪代码如下：注意算M时要+1，防止向下取整时发生死循环

while l<r:
    m = l + r + 1 >> 1  # 等同(l+r+1)//2
    if m红:
        l = m  # l=m时，需要+1
    else:
        r = m - 1

第二类：ans是绿色区间的左端点(ans<=x)

将[L,R]分为[L,M]和[M+1,R]

if M是绿色的，说明ans在区间[L,M]

else 说明ans在区间[M+1,R]

伪代码如下：

while l<r:
    m = l + r  >> 1  # 等同(l+r)//2
    if m绿:
        r = m  # l=m时，不需要+1
    else:
        l = m + 1

2. 方法二  

思路：

1. 更据题目最后要求的量划分二分区域找到隔板

2. 套模板，思考isBlue函数应该怎么写，也就是什么是时候选择区间的左半部分。l和r的初始值需要比整个区间小1和大1。

3. 最后的值是l还是r

代码模板，每次根据题意改变isBlue函数：

def isBlue(n):
    if n<target:
        return True
    else:
        return False
nums = [5,7,7,8,8,10]
target = 8
l=-1
r=len(nums)
while l+1!=r:
    mid=l+r>>1
    if isBlue(nums[mid]):
        l=mid
    else:
        r=mid
print(l,r)

---

二、二分例题

1. 数的范围

n,q=map(int,input().split())
s=list(map(int,input().split()))
for i in range(q):
    find=int(input())
    #左边界
    l=0
    r=n-1
    while l<r:
        mid= l+r>>1 #等同(l+r)//2
        if s[mid]>=find: 
            r=mid #r=mid时，不需要要+1
        else:
            l=mid+1
    if s[l]==find: #注意是l不是mid
        print(l,end=" ")
    else:
        print(-1,end=" ")
    #右边界
    l = 0
    r = n - 1
    while l < r:
        mid = l + r + 1 >> 1
        if s[mid] <= find:
            l = mid
        else:
            r = mid - 1
    if s[l] == find:
        print(l)
    else:
        print(-1)
 

2. 分巧克力

要点：

1.每块巧克力分的时候不可以拼接
2.每个人分得的巧克力大小相同
3.二分方法：以需要分的数量k作为临界点，当分的大小<=最大值时，sum(分得的巧克力数量)>=k

n,k=map(int,input().split())
h=[]
w=[]
for i in range(n):
    a,b=map(int,input().split())
    h.append(a)
    w.append(b)
def check(m):
    sum=0
    for i in range(n):
        sum+=(h[i]//m)*(w[i]//m)#计算分的巧克力的总量
    if sum>=k:
        return True
    else:
        return False
#以需要分的数量k作为临界点，当分的大小<=最大值时，sum(分得的巧克力数量)>=k
l=1
r=100000
while l<r:
    m=l+r+1>>1
    if check(m):
        l=m
    else:
        r=m-1
print(l)

---

三、前缀和

利用数列的前n项和来求下标从L，R和的值

四、前缀和例题

1. 子矩阵的和

思路：

1. 如何计算前缀和矩阵

2. 如何计算询问的结果

n, m, q = map(int, input().split())
grid=[[0 for i in range(m+1)]for j in range(n+1)]
sum_grid=[[0 for i in range(m+1)]for j in range(n+1)] #前缀和矩阵
#输入
for i in range(n):
    a=list(map(int,input().split()))
    for j in range(m):
        grid[i+1][j+1]=a[j]
#计算前缀和
for i in range(1,n+1):
    for j in range(1,m+1):
        sum_grid[i][j]=sum_grid[i][j-1]+sum_grid[i-1][j]+grid[i][j]-sum_grid[i-1][j-1]
result=[]
#输出查询结果
for i in range(q):
    x1,y1,x2,y2=map(int, input().split())
    sum=sum_grid[x2][y2]-sum_grid[x2][y1-1]-sum_grid[x1-1][y2]+sum_grid[x1-1][y1-1]
    result.append(sum)
for i in result:
    print(i)