二分答案的应用

二分答案

P8647 [蓝桥杯 2017 省 AB] 分巧克力

题目描述

儿童节那天有 $K$ 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 $N$ 块巧克力，其中第 $i$ 块是 $H_i \times W_i$ 的方格组成的长方形。

为了公平起见，小明需要从这 $N$ 块巧克力中切出 $K$ 块巧克力分给小朋友们。切出的巧克力需要满足：

1. 形状是正方形，边长是整数。

2. 大小相同。

例如一块 $6 \times 5$ 的巧克力可以切出 $6$ 块 $2 \times 2$ 的巧克力或者 $2$ 块 $3 \times 3$ 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小 $H_i$ 计算出最大的边长是多少么？

输入格式

第一行包含两个整数 $N$ 和 $K$。$(1 \le N,K \le 10^5)$。

以下 $N$ 行每行包含两个整数 $H_i$ 和 $W_i$。$(1 \le H_i,W_i \le 10^5)$。

输入保证每位小朋友至少能获得一块 $1 \times 1$ 的巧克力。

输出格式

输出切出的正方形巧克力最大可能的边长。

输入输出样例 #1

输入 #1

2 10  
6 5  
5 6

输出 #1

2

说明/提示

蓝桥杯 2022 省赛 A 组 I 题。

解决方案

首先我们来了解一下所谓的二分答案算法。

我的个人理解是，二分答案算法主要应用于在有多种答案满足题意时求答案的最值，即哪个答案最大或者哪个答案最小。以上述题目为例，从切出边长为1的小正方形到切出以所有H和W中的最大值maxi为边长的小正方形，答案的可能区间即为[1, maxi]。而我们就是要在这个区间内使用朴素二分搜索算法将我们要找到的最值求出，即为二分答案算法。

# 判断当下的值是否为答案之一
def check(x):
  count = 0
  for h, w in chs:
    count1 = h // x
    count2 = w // x
    count += count1 * count2

  return count >= k

if __name__ == "__main__":
  n, k = map(int, input().split())

  chs = []
  maxi = 0
  for i in range(n):
    h, w = map(int, input().split())
    maxi = max(max(h, w), maxi)
    chs.append((h, w))

  # 二分
  ans, low, high = 0, 1, maxi
  while low <= high:
    mid = int((low + high) / 2)

    if check(mid):
      ans = max(ans, mid)
      low = mid + 1
    else:
      high = mid - 1

  print(ans)

Bingo!

P1024 [NOIP 2001 提高组] 一元三次方程求解

题目描述

有形如：$a x^3 + b x^2 + c x + d = 0$ 这样的一个一元三次方程。给出该方程中各项的系数（$a,b,c,d$ 均为实数），并约定该方程存在三个不同实根（根的范围在 $-100$ 至 $100$ 之间），且根与根之差的绝对值 $\ge 1$。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 $2$ 位。

提示：记方程 $f(x) = 0$，若存在 $2$ 个数 $x_1$ 和 $x_2$，且 $x_1 < x_2$，$f(x_1) \times f(x_2) < 0$，则在 $(x_1, x_2)$ 之间一定有一个根。

输入格式

一行，$4$ 个实数 $a, b, c, d$。

输出格式

一行，$3$ 个实根，从小到大输出，并精确到小数点后 $2$ 位。

输入输出样例 #1

输入 #1

1 -5 -4 20

输出 #1

-2.00 2.00 5.00

说明/提示

【题目来源】

NOIP 2001 提高组第一题

解决方案

显然此题需要从-100到100之间枚举，但是题目中给出的根与根之差的绝对值≥1说明在一个长度为1的区间内不可能有两个根，因此我们可以将一个长度为1的区间作为我们的最小枚举单位，在此单位内进行二分查找。

def cal(x):
  return a * x ** 3 + b * x ** 2 + c * x + d

if __name__ == "__main__":
  a, b, c, d = map(float, input().split())

  count = 0
  anss = []
  # 在可能的取值范围内枚举
  for i in range(-100, 101):
    # 最小枚举单位的长度为1
    low, high = i, i+1
    res1, res2 = cal(low), cal(high)

    if res1 == 0:
      anss.append(low)
      count += 1

    if res1 * res2 < 0:
      # 二分查找时，若值类型为浮点数，最好不要将边界条件设置为0
      # 否则容易超时
      while high - low >= 0.001:
        mid = (high + low) / 2

      # 说明前半段中有根，右边界应该内收
        if cal(mid) * res1 <= 0:
          high = mid
        else:
          low = mid
      # 最后右端点一定就是根
      anss.append(high)
      count += 1

    if count == 3:
      break

  for ans in anss:
    print("{:.2f}".format(ans), end=" ")

Bingo！