Acg | 0x04 | 忆の風

一、整数二分

Demo

Explain

将模板分为二种情况,循环以l=r结束
看第一段，若 $a[mid]\geq{x}$ ,因为是单增序列，推出 mid 后面的数会更大，所以缩小区间为左半段,又 mid 也可能是答案，因此r=mid
为什么采用右移运算，而不是除法。右移是向下取整，整除是向零取整，在值域包含负数的时候后者没法正常工作。

Code

在单增序列 a 中查找 $\geq{x}$ 中最小的那个

1
2
3
4
5
6


while l<r:
	mid=l+r>>1
	if a[mid]>=x:
		r=mid
	else:
		l=mid+1

在 a 中找 $\leq{x}$ 中最大的那个

1
2
3
4
5
6


while l<r:
	mid=l+r+1>>1
	if a[mid]<=x:
		l=mid
	else:
		r=mid-1

E1 数的范围

topic

给定一个按照升序排列的长度为 n 的整数数组,以及 q 个查询。对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。如果数组中不存在该元素，则返回 -1 -1.

analyse

先用模板找起始位置，即最小的那个。
如果s[l]!=x,说明没找到，输出-1 -1即可，
否则，输出起始，再用模板找终止位置即可。

code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


n,q=map(int, input().split())
s=list(map(int, input().split()))

while q:
q-=1
x=int(input())

l,r=0,n-1
while l<r:
    mid =l+r>>1
    if s[mid]>=x: r=mid
    else: l=mid+1

if s[l]!=x:
    print('-1 -1')
else:
    print(l,end=' ')
    l,r=0,n-1
    while l<r:
        mid=l+r+1>>1
        if s[mid]<=x: l=mid
        else: r=mid-1
    print(l)

二、实数二分

Demo

Explain

确定精度eps.如果需要保留 k 位小数， $eps=1e-(k+2)$

Code

1
2
3
4
5
6


while l+1e-5<r:
	mid=(l+r)/2
	if calc(mid):
		r=mid
	else:
		l=mid

E1 数的三次方根

题目

给定一个浮点数 n，求它的三次方根。

code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


x=float(input())
N=1e4
l,r=-N,N
while l+1e-8<r:
mid = (l+r)/2
if mid**3>=x:
    r=mid
else:
    l=mid
print("%.6f" % l)

三、二分答案转换成判定

Explain

题目中出现类似于“最大值最小”的含义，这是答案具有单调性，可用二分转化成判定的特征之一

E1 最佳牛围栏

思考

转换题目：给定正整数数列 A,求一个平均数最大且长度不小于 L 的连续子段.
如果 mid 是答案，判定“是否存在一个长度不小于 L 的子段，平均数不小于二分的值”
如果每个数都减去 mid,那么就转化为，“是否存在一个长度不小于 L 的子段，子段和>=0”
如果存在，则更新l=mid,因为答案肯定在右边

code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


n,f=map(int, input().split())
cow=[0]
sum=[0]\*(n+1)
for i in range(1,n+1):
cow.append(int(input()))

    def check(mid):
        # 要逐次-mid
        for i in range(1,n+1):
            sum[i] = sum[i-1]+cow[i]-mid

        minv=0 # 因为sum[0]是0
        i,j=0,f
        while j<=n:
            minv = min(minv, sum[i]) #记录之前的最小值
            if sum[j]-minv>=0: # 说明有合法方案
                return True
            j+=1;i+=1
        return False

    l,r=0,2000
    while l+1e-5<r:
        mid=(l+r)/2
        if check(mid): # 说明存在平均值不小于二分的值，所以要取右半边
            l=mid
        else:
            r=mid
    print(int(r*1000))

E2 防线

思考

code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


T = int(input())
while T:
    T-=1

    s=[]
    n=int(input())
    l,r=0,0
    for i in range(n):
        ss,e,d=map(int, input().split())
        s.append([ss,e,d])
        r=max(r, e)

    def getsum(x):
        res=0
        for i in s:
            if i[0]<=x:
                res += (min(i[1], x) - i[0]) // i[2] + 1
        return res

    while l<r:
        mid = l+r>>1
        if getsum(mid)%2: #如果是奇数,答案肯定在左半边
            r=mid
        else:
            l=mid+1

    sum = getsum(r)-getsum(r-1)
    if sum%2:
        print(r,sum)
    else:
        print("There's no weakness.")