主页 / 问题 / 1539820
Accepted
Nymos
Asked:2023-09-09 22:01:13 +0000 UTC2023-09-09 22:01:13 +0000 UTC

帮我解决一个Python难题！

  • 772

大家下午好。我正在用 Python 解决一个问题，但我不知道错误是什么。这是任务本身：

问题1.5。处理请求[实施；数据结构; 两个指针；二分搜索] Alice 正在设计一个计算系统，旨在处理大量相似的查询。设计的系统将包含一定数量的相同处理器。在任何给定时间，每个处理器都可以空闲或忙于处理一个请求。所有请求的处理时间相同，均为 s 毫秒。系统必须实时运行，也就是说，每个传入的请求必须立即转移到任何空闲处理器进行处理。

Alice 想要了解一个计算系统应该包含多少个处理器。为此，她收集了过去类似系统性能的统计数据。每个数据集都包含 n数字t1, t2,…,tn，其中ti是收到带有数字的请求的时刻i。集合中的数字可以重复，但是它们按非递减顺序排序。如果处理器在 时间 开始处理请求ti，那么在 时间t i +s它将能够开始处理新请求。

该集合可能包含相当大量的数据，因此您需要编写一个程序来确定计算系统中必须存在的最小处理器数量，以便所有请求到达时都得到处理。

输入数据格式 第一行输入包含两个自然数n和s- 请求数和一个请求的处理时间， 1≤n≤200000, 1≤s≤10⁹。第二行包含非负整数 t1,t2,…,tn，指定接收请求的时间0 ≤ t1 ≤ t2 ≤ ⋯≤ tn ≤ 10⁹。

输出格式 打印一个数字 - 在收到请求时允许处理所有请求的处理器的最小数量。

测试方法 该程序使用 30 次测试进行测试。通过每项测试得 1 分。验证期间不使用任务条件的测试。下表显示了可能的测试用例。 在此输入图像描述

示例输入 1：9 30 90 90 90 120 120 120 120 200 200

样本输出 1:4

示例输入 2：10 30 0 25 110 125 125 130 140 140 140 155

样本输出 2:6

示例说明 第一个示例对应于第一个测试用例。在时间 120，四个请求同时到达，其处理将需要四个处理器。

第二个示例中的查询执行计划可以表示在下表中。 在此输入图像描述 五个处理器将不再足以及时处理所有请求。

这是我的代码：

def min_processors(n, s, t):
    i_s = 0
    i_f = 1
    cnt = 1

    while i_s < n - 1:
        if t[i_f] + s <= t[i_s]:
            cnt -= 1
            i_f += 1
        else:
            cnt += 1
            i_s += 1

    return cnt

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

result = min_processors(n, s, t)
print(result)
python

2 个回答

  1. Best Answer

    你的开始时刻是有序的并且处理时间是恒定的 - 这很好，问题被简化了，它可以在线性时间内解决。

    我们要遵守指示два указателя

    我们将在第一个间隔开始后开始工作。您为间隔的i_s = 1开始和结束启动两个索引。i_f = 0启动活动间隔计数器cnt=1

    在循环中，您检查哪个先出现 -t[i_f]+s或t[i_s]。当相等时，首先处理末端 - 这可以通过使用简单地实现<=-if t[i_f]+s <= t[i_s]

    当处理结束时你会做cnt -= 1并且i_f +=1

    当处理开头时，你会做cnt += 1并且i_s +=1

    达到的最大值cnt就是期望的结果。

    def min_processors(n, s, t):
    i_f = 0
    i_s = 1
    cnt = 1
    max_cnt = 1

    while i_s < n:
        if t[i_f] + s <= t[i_s]:
            cnt -= 1
            i_f += 1
        else:
            cnt += 1
            max_cnt = max(max_cnt, cnt)
            i_s += 1

    return max_cnt

n, s = 9, 30
#t = list(map(int, "90 90 90 120 120 120 120 200 200".split()))
n, s = 10, 30
t = list(map(int, "0 25 110 125 125 130 140 140 140 155".split()))

result = min_processors(n, s, t)
print(result)
    • 2

  2. 您的代码不考虑第一个任务的结束（索引i_f以 1 开头）和最后一个任务的开始（索引i_s以n - 2结尾）。对于n = 3、s = 1、t = [0, 10, 20] ，您返回3，尽管作业很短并且一个处理器就足够了。

    让我们完美地解决这个问题吧。这当然是扫荡。一半的事件是处理请求的时间：

    es = ((ti, 1) for ti in t)

    后半部分是请求处理的结束时间：

    ef = ((ti + s, -1) for ti in t)

    它们需要以共同的顺序收集。堆q.合并：

    e = heapq.merge(es, ef)

    一旦混合，就不需要时间戳。我们只保留复选框：

    e = (c for _ , c in e)

    为了找到每个时刻所需的处理器数量，我们来计算累计总和。itertools.accumulate：

    a = itertools.accumulate(e)

    我们需要最大值：

    max(a)

    一起：

    import heapq
import itertools

_, s = map(int, input().split())
t = tuple(map(int, input().split()))
print(max(itertools.accumulate(
    c
    for _ , c in heapq.merge(
        ((ti    ,  1) for ti in t),
        ((ti + s, -1) for ti in t)
    )
)))
    • 0

相关问题