主页 / 问题 / 1609577
Accepted
user27630724
Asked:2025-03-30 03:25:06 +0000 UTC2025-03-30 03:25:06 +0000 UTC

按答案进行二进制搜索。寻找最大长度的问题

  • 772

有n根绳子，你需要把它们剪成k段长度相同的绳子。找出可以获得的碎片的最大长度。

输入数据第一行包含两个数字——n和k（1≤n，k≤10000）。另外，在接下来的 n 行中，每行写一个数字——下一根绳子的长度 ai (1≤ai≤107)。

输出打印一个实数 - 可以获得的碎片的最大长度。如果相对误差或绝对误差不超过 10−6，则答案将被视为正确。

Пример

Входные данные

4 11
802
743
457
539

Выходные данные
200.5

n, k = map(int, input().split())
def bina_(sp,n,k): # поиск целого числа
    i = 0
    r = 10 ** 7 + 1
    while r > i + 1:
        sr = (i + r) // 2
        if proveri_(sr,sp,k) == 1:
            i = sr
        else:
            r = sr
    return i

def bina_s(sp,a,k): # поиск числа после точки
    i = 0
    r = 9999999999
    while r > i + 1:
        sr = (i + r) // 2
        if proveri_s(sp,a,k,sr) == 1:
            i = sr
        else:
            r = sr
    return i
def proveri_s(sp,a,k,sr):
    co_ = 0
    for i in sp:
        co_ += int(i // float(f'{a}.{sr}'))
    if co_ >= k:
        return 1

def proveri_(sr,sp,k):
    co_ = 0
    for i in sp:
        co_ += (i // sr)
    if co_ >= k:
        return 1

sp = []
for i in range(n):
    sp.append(int(input()))
    
a = bina_(sp,n,k)
b = bina_s(sp,a,k)
print(float(f'{a}.{b}'))

简化代码

n, k = map(int, input().split())
def bina_(sp,n,k):
    i = 1
    r = 10 ** 7 + 1
    for _ in range(1000):
        sr = (i + r) / 2
        if proveri_(sr,sp,k) == 1:
            i = sr
        else:
            r = sr
    return i

def proveri_(sr,sp,k):
    co_ = 0
    for i in sp:
        co_ += (i // sr)
    if co_ >= k:
        return 1

sp = []
for i in range(n):
    sp.append(int(input()))

a = bina_(sp,n,k)
print(a)
python

2 个回答

  1. Best Answer

    二进制搜索循环必须运行，直到相对或绝对误差小于或等于百万分之一。在这种情况下，误差是剩余范围的宽度（除以相对误差的上限）

    i = 0
r = 10 ** 7 + 1
while ((r-i)/r > 1E-6) and (r-i > 1E-6):
    • 1

  2. 第一个代码没有寻找不超过 10−6 的相对或绝对误差。修改后的代码：我使用 for _ in range(100) 实现了相对或绝对误差：

        i = 0
    r = 10 ** 7 + 1
    for _ in range(100):
        sr = (i + r) / 2
        if proveri_(sr,sp,k) == 1:
            i = sr
        else:
            r = sr
    return i

def proveri_(sr,sp,k):
    co_ = 0
    for i in sp:
        co_ += (i // sr)
    if co_ >= k:
        return 1


a = bina_(sp,n,k)
print(a)
    • 0

相关问题