在不到 5 秒内将代码优化为运行

Question

在 HackerEarth 上的一些测试用例中，以下代码需要超过 5 秒 (5.001)。如何在不到 5 秒的时间内将此代码优化到运行？

tc = int(input())
ip = []
for x in range(0, tc):
    temp = []
    temp.append(int(input()))
    temp.append([int(n) for n in input().split()])
    temp.append(int(input()))
    ip.append(temp)

for it in ip:
    while not it[2] <= 0:
        for x in range(0, it[0]):
            if it[1][x] == '0':
                continue
            it[2] -= int(it[1][x])
            if it[2] <= 0:
                it.append(x+1)
                break
    print(it[3])

仅供参考：

问题陈述

Aniruddha 被给予了一个里程碑 M 来达到距离。他生活在一个不同的银河系，那里有 N 天 year.At 第 i 天他最多可以走路 X distance.Assuming 他走路最优化你需要输出他达到里程碑的最少天数.

输入

第一个输入行包含 T 个测试用例。每个测试用例包含三行第一行包含一个整数 N — 一年中的天数。

下一行包含 N 个非负数 space 分隔的数字——即 Aniruddha 第 i 天要走的距离。保证至少有一个数大于零。

第三行是Aniruddha必须达到的里程碑值。

输出

对于每个测试用例，您需要输出以下查询的答案。

约束

1<=T<= 10

1<=N<=10^5

0<=X<=10^8

0<=M<=10^16

Answer 1

假设这个问题来自here，目标是找出在一年中的哪一天达到里程碑。因此，我们只对达到里程碑所需的最后一年真正感兴趣。

因此，只需使用 % 运算符找出去年还剩多少距离，即可显着提高代码速度：

remainder = target % dist_per_year

然后可以使用与最初使用的相同方法迭代余数。示例（写在python 2.7）：

import random as rand
import time


def testcase(dist, milestone):
    dist_per_year = sum(dict)
    remainder = milestone % dist_per_year

    if remainder == 0:
        return len(dist)

    day = 0
    while remainder > 0:
        day = day + 1
        remainder = remainder - dist[day - 1]

    return day


milestone = rand.randint(0, 10e16)
days = rand.randint(1, 10e5)
dist = [rand.randint(0, 10e8) for i in xrange(days)]

t0 = time.time()
day = testcase(dist, milestone)
print 'Day:', day
print 'Time:', time.time() - t0

Answer 2

感谢 J。 Hollom，我做了一些修改，把代码移植成了Python3.x。请注意我的代码是为 Hacker Earth 设计的（link 由 J. Hollom 提供）因此它需要输入！

test_cases = int(input())
inputs = []
for x in range(test_cases):
    temp = []
    temp.append(int(input()))
    temp.append([int(n) for n in input().split()])
    temp.append(int(input()))
    temp.append(sum(temp[1]))
    inputs.append(temp)


for item in inputs:
    item[2] = item[2] % item[3]
    if item[2] == 0:
        item[2] += item[3]
    day = 0
    while item[2] > 0:
        item[2] -= item[1][day]
        day += 1 # Since day begins at Day 1 this will give right answer!
    print(day)

好了，现在所有输入运行不到 1 秒！

在不到 5 秒内将代码优化为运行

Optimize the code to run in less than 5 second

optimization

mathematical-optimization

python-3.x

问题陈述

输入

输出

约束

在不到 5 秒内将代码优化为 运行

Optimize the code to run in less than 5 second

optimization

mathematical-optimization

python-3.x

问题陈述

输入

输出

约束

在不到 5 秒内将代码优化为运行