More efficient solution to search a python list-CodePudding

code:

#!/usr/bin/env python
import sys
sys.setrecursionlimit(1000000000)



# N is the number of available days.
N = None

# F is the amount of fuel available.
F = None

# C contains the fuel needed to open a portal on each day.
C = [None for x in range(100005)]

answer = None

# Open the input and output files.
input_file = open("spacein.txt", "r")
output_file = open("spaceout.txt", "w")

# Read the value of N and F.
input_line = input_file.readline().strip()
N, F = map(int, input_line.split())

# Read the cost to open a portal on each day.
for i in range(0, N):
    C[i] = int(input_file.readline().strip())



fuel = []
for i in range(0, N):
    fuel.append(C[i])

print(fuel)
final = []

for i in range(0, len(fuel)-2):
    for j in range(i 1, len(fuel)):
        if fuel[i]   fuel[j] < F or fuel[i]   fuel[j] == F:
            final.append(fuel.index(fuel[j])-fuel.index(fuel[i]))
            print(fuel.index(fuel[i]), fuel.index(fuel[j]))
        else:
            pass
if len(fuel) > 2:
    answer = (max(final) 1)
else:
    answer = -1

# Write the answer to the output file.
output_file.write("%d\n" % (answer))

# Finally, close the input/output files.
input_file.close()
output_file.close()

CodePudding user response：

The second sample input has a more insightful daily consumptions list:

F = 14
C = [12, 8, 2, 16, 4, 6, 10]

Note that you definitely wouldn't start on the day with consumption 16 even if F were larger, as the earlier days cost less and give more. Only 12, 8 and 2 are viable start days due to this reason.

So go through the days and keep decreasing consumption entries along with their original indexes (i.e., their dates). And for each day as possible end day, binary search that list. For example for the day with consumption 4 as end day, you can afford 14-4=10 for a start day. Binary search 10 in [12, 8, 2] to find the 8.

Accepted code (I negated the consumption values because bisect wants an increasing list):

from bisect import bisect_left

with open('spacein.txt') as f:
    _, F, *C = map(int, f.read().split())

S = []
I = []
best = -1
for i, c in enumerate(C):
    j = bisect_left(S, c - F)
    if j < len(S):
        best = max(best, i - I[j]   1)
    if not S or c < -S[-1]:
        S.append(-c)
        I.append(i)

with open('spaceout.txt', 'w') as f:
    print(best, file=f)

CodePudding user response：

I think you can make your program faster by simply changing the line C = [None for x in range(100005)] to C = [] and then in your loop change C[i] = int(input_file.readline().strip()) to C.append(int(input_file.readline().strip())). Since that way you wont loop 100005 times just to put a None value into the C array. Also, I don't see why you need the C array at all, since you only use it to fill the fuel array? I would just read the portal costs for each day directly into the fuel array so you reduce redundancies, that way you will have one less N loop in your code.