Last time It's the third day.
#3 Problem
** Thoughts ** 1WA, 4TLE (WA submitted a mistake) The biggest enemy this time was TLE. I don't have an image of computational complexity, but I didn't know the internal implementation of Python. Looking at the problem, I got a habit of sorting the problem of finding the maximum and minimum values for the time being. At first, I thought that the minimum value would come out if I subtracted in order with for,
l = [10,15,11,14,12]
l.sort(reverse=True) #l = [15,14,12,11,10]
ans = l[0]
for i in range(n-1):
ans = min(l[i+1] - l[i],ans)
I thought it would work with. However, it is necessary to find the minimum value among k selected from n. Therefore, it is necessary to extract k sorted inputs and max-min among them. When I thought about how to take k by k, I used slices because the Python list has slices. This was a big mistake. Apparently ** Python slicing takes ultra time when done on large objects **. If you know the reason, please let me know. Is it taking a long time to access the object? So, the one who TLE using slices
n, k = map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort(reverse=True)
seed = h[0]
for i in range(0,n-k+1):
high = h[i:i+k][0] - h[i:i+k][k-1] #here
seed = min(high,seed)
print(seed)
I'm spending time slicing the comment part. Even if I mean it, tax_free that I want to slice has been TLEed 4 times. If you think about it now, you can specify it by index without slicing it separately.
It turned out that the slice was eating for a long time, so this is what I specified in the index
n, k = map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort(reverse=True)
seed = h[0]
for i in range(0,n-k+1):
high = h[i] - h[i+k-1]
seed = min(high,seed)
print(seed)
Not sliced.
I didn't understand how Python feels. From now on, specify by index directly without using slices. see you
Recommended Posts