主页 / 问题 / 1596049
Accepted
user27630724
Asked:2024-10-08 17:05:55 +0000 UTC2024-10-08 17:05:55 +0000 UTC

使用二分搜索优化代码

  • 772

关于此任务已经提出了有关优化的问题，但是仍然可以通过使用这部分代码来优化代码而不连接任何库吗？

while j + c - 1 < len(mass):
    if mass[j + c - 1] - mass[j] <= m:
        k += 1
        j = j + c
    else:
        j = j + 1

问题编号 1620。苏博尼克

班上还有人在学习N。班主任接到指示，各派一R组С人去清理。所有参与清理工作的团队都将从事搬运原木的工作。每根原木均由一个团队的所有成员同时搬运。在这种情况下，该大队成员的身高差异越小，携带原木就越方便。

团队的不便数将是该团队中最高和最矮成员的身高差（如果团队中只有一个人，则该差值等于0）。班主任决定组队，尽量将组队带来的不便降到最低。帮帮他吧！

考虑以下示例：

设班上有身高厘米为、、、、、、、、、的人，8需170分成两队，每队三人。205225190260130225160

那么一种选择是这样的：

第一大队：身高225、205、225的人

第二大队：身高160、190、170的人

在这种情况下，第一队的不便次数将等于20，第二队的不便次数将等于30。不便数的最大值将为30，这将是最好的结果。

输入格式

首先输入自然数N，R以及C- 班级人数、小组人数和每队人数（1 ≤ R∙C ≤ N ≤ 100 000）。接下来，N输入整数 - 每个N学生的身高。学生的身高是一个不超过的自然数1 000 000 000。

输出格式

打印一个数字 - 所组成的团队的最大不便次数的最小可能值。

n, r, c = map(int, str(input()).split())
mass = []
for i in range(n):
    mass.append(int(input()))
mass = sorted(mass)
right = mass[len(mass) - 1] - mass[0]
left = 0
while left < right:
    m = (left + right) // 2
    j = 0
    k = 0
    while j + c - 1 < len(mass):
        if mass[j + c - 1] - mass[j] <= m:
            k += 1
            j = j + c
        else:
            j = j + 1
    if k >= r:
        right = m

    else:
        left = m + 1

print(right)
python

3 个回答

  1. Best Answer

    常数可以改进，大O将保持不变。我不确定这是否有帮助，但我想不出更好的办法。

    inconv- 给所有可能的团队带来一系列不便。是根据学生订购的身高来计算的。

    pred(i)检查是否有可能招募r团队，且不便程度不超过i。拨打r队电话后立即返回该值。

    二分搜索在[min(inconv), max(inconv)]范围内进行。

    n, r, c = map(int, str(input()).split())

h = sorted(int(input()) for _ in range(n))
inconv = [h[j] - h[i] for i, j in zip(range(n - c + 1), range(c - 1, n))]


def pred(i):
    k = 0
    j = 0
    while j < len(inconv):
        if inconv[j] <= i:
            k += 1
            if k >= r:
                return True
            j += c
        else:
            j += 1
    return False


low = min(inconv)
high = max(inconv)

# assert not pred(inconv[:low]) and pred(inconv([high:])
while low < high:
    mid = (low + high) // 2
    if pred(mid):
        # assert pred(inconv([mid:])
        high = mid
        # assert pred(inconv([high:])
        # assert not pred(inconv[:low]) and pred(inconv([high:])
    else:
        # assert not pred(inconv([:mid + 1])
        low = mid + 1
        # assert not pred(inconv([:low])
        # assert not pred(inconv[:low]) and pred(inconv([high:])
        
    # assert not pred(inconv[:low]) and pred(inconv([high:])

# assert not pred(inconv[:low]) and pred(inconv([high:])
# assert low == high
# assert not pred(inconv[:low]) and pred(inconv([low:])

print(low)
    • 3

  2. 我们创建一个不便字典，以第一个和最后一个组索引的总和作为键。我们以最小的不便找到了钥匙。我们在不相交的组中寻找下一个最小的不便，并找到第一个最小的不便。这有点令人困惑，但如果有人感兴趣，我可以更详细地描述它：

    n, r, c = 8, 2, 3
mass = [170, 205, 225, 190, 260, 130, 225, 160]
mass.sort()
inconv = {a + b: mass[b] - mass[a] for a,b in enumerate(range(c-1,len(mass)))}
out_scope = 2 * c
# Сортируем ключи словаря по значениям. Умышленно создаем список, дабы дважды
# не создавать генератор сортировки по всему словарю. Жертвуем памятью для скорости.
sorted_keys = sorted(inconv.keys(), key=lambda _key: inconv[_key])
for min_key in sorted_keys:
    # Отбираем значение первого непересекающегося диапазона. Остальные игнорируем за счет одношагового генератора.
    result= next((inconv[key] for key in sorted_keys if abs(key - min_key) >= out_scope), None)
    # Если генератор оказался пустым, продолжаем поиски, иначе результат найден. Досрочно выходим
    if result:
        break
print(result)
    • 0

  3. 或者：

    # Тесты
# n, r, c = map(int, '8 2 3'.split())
# mass = [170, 205, 225, 190, 260, 130, 225, 160]
# n, r, c = map(int, '7 2 3'.split())
# mass = [1, 1, 2, 2, 2, 3, 3]

n, r, c = map(int, input().split())
mass = [int(input()) for _ in range(n)]

mass.sort()

crews = tuple(
    crew[-1] - crew[0] for i in range(len(mass)+1-c) if (crew := mass[i:i+c])
    )

resu = set()
while r > 0:
    min_mid = min(crews)
    resu.update((min_mid,))
    count = crews.count(min_mid)
    if (r := r - count) > 0:
        crews = tuple(x for x in crews if x != min_mid)
else:
    print(max(resu))
    • 0

相关问题