主页 / 问题 / 1569720
Accepted
Mokybrow
Asked:2024-03-02 03:21:15 +0000 UTC2024-03-02 03:21:15 +0000 UTC

如何优化 Python 中的算法？

  • 772

我正在解决 Yandex 前几年的问题，但仍然无法通过大量数据的测试，随着时间的推移它会下降。任务本身 在此输入图像描述

我的代码：

n = int(input())
orders = []
for i in range(n):
    start = list(map(int, input().split()))
    orders.append(start)

q = int(input())
queries = []
for i in range(q):
    start = list(map(int, input().split()))
    queries.append(start)


results = []
for query in queries:
    query_type = query[-1]
    if query_type == 1:
        start_time = query[0]
        end_time = query[1]
        total_cost = 0
        for order in orders:
            order_start_time = order[0]
            if order_start_time >= start_time and order_start_time <= end_time:
                total_cost += order[2]
        results.append(total_cost)
    elif query_type == 2:
        start_time = query[0]
        end_time = query[1]
        total_duration = 0
        for order in orders:
            order_end_time = order[1]
            if order_end_time >= start_time and order_end_time <= end_time:
                total_duration += order[1] - order[0]
        results.append(total_duration)

print(*results)

输入和输出数据示例

进入

1
10 100 1000
6
1 10 1
1 10 2
10 100 1
10 100 2
100 1000 1
100 1000 2

结论

1000 0 1000 90 0 90

进入

5
5 20 5
6 21 4
6 22 3
7 23 2
10 24 1
3
6 11 1
4 6 1
7 11 1

结论

10 12 3
python

3 个回答

  1. Best Answer

    扫地。活动按时间和活动类型组织。

    事件类型 意义
    0 请求期开始
    1 订单开始或结束
    2 请求期结束

    对类型进行排序，以便请求周期是一个闭区间。

    状态：累计值totals[0]和累计时长totals[1]。

    事件 行动
    订单开始 累积价值增加。
    订单结束 增加累积持续时间。
    请求类型1的开始 用减号保存订单中的累计成本。
    请求类型1结束 为订单添加累积价值。订单包含订单开始和结束时累计成本之间的差额。
    请求类型2的开始 用减号按顺序保存累计持续时间。
    请求类型2结束 将累积持续时间添加到订单中。订单包含订单开始和结束时累积持续时间之间的差值。

    解决方案的复杂度为 O((n + q)log(n + q))。大部分时间都花在排序上。扫描本身是线性的。空间复杂度O(n + q)。

    events = []
totals = [0, 0]


def make_total_increment(i, v):

    def f():
        totals[i] += v

    return f


n = int(input())

for _ in range(n):
    s, e, c = map(int, input().split())
    events.append((s, 1, make_total_increment(0, c)))
    events.append((e, 1, make_total_increment(1, e - s)))

q = int(input())

queries = [0] * q


def make_query_increment(i, j):

    def f():
        queries[i] += totals[j]

    return f


def make_query_decrement(i, j):

    def f():
        queries[i] -= totals[j]

    return f


for i in range(q):
    s, e, t = map(int, input().split())
    if t == 1:
        events.append((s, 0, make_query_decrement(i, 0)))
        events.append((e, 2, make_query_increment(i, 0)))
    else:
        events.append((s, 0, make_query_decrement(i, 1)))
        events.append((e, 2, make_query_increment(i, 1)))

for _, _, f in sorted(events, key=lambda v: v[:2]):
    f()

print(*queries)
    • 1 
  2. n = int(input())
orders = [list(map(int, input().split())) for _ in range(n)]

q = int(input())
queries = [list(map(int, input().split())) for _ in range(q)]

results = []
for query in queries:
    query_type = query[-1]
    start_time = query[0]
    end_time = query[1]
    total = 0

    if query_type == 1:
        for order in orders:
            if start_time <= order[0] <= end_time:
                total += order[2]
    elif query_type == 2:
        for order in orders:
            if start_time <= order[1] <= end_time:
                total += order[1] - order[0]

    results.append(total)

print(*results)

    将循环替换为列表推导式以创建订单和查询列表，因为这更高效且更具可读性。还将计算总计的条件合并到一个循环中，以避免代码重复并加快程序执行速度。

    • 0

  3. 由于查询涉及的是间隔的总和，因此我们将按时间对初始值进行排序并保存累积总和。要计算区间上的总和，您需要找到区间的左端和右端，并减去两端的累积和。

    该算法的复杂度为 O((n + q)logn)。nlogn - 顺序排序，qlogn - 查询执行。空间复杂度O(n)。

    import bisect


def make_range_sum(points):
    x, y = zip(*sorted(points))
    
    ys = [0]
    for yi in y:
        ys.append(ys[-1] + yi)

    def range_sum(a, b):
        i = bisect.bisect_left(x, a)
        j = bisect.bisect_right(x, b)
        return ys[j] - ys[i]

    return range_sum


costs = []
durations = []

n = int(input())

for _ in range(n):
    s, e, c = map(int, input().split())
    costs.append((s, c))
    durations.append((e, e - s))

range_sums = None, make_range_sum(costs), make_range_sum(durations)

for i in range(int(input())):
    if i > 0:
        print(end=' ')
    s, e, t = map(int, input().split())
    print(range_sums[t](s, e), end='')
print()
    • 0

相关问题