Täglicher AtCoder # 3 in Python

Einführung

Letztes Mal Es ist der dritte Tag.

** Gedanken ** 1WA, 4TLE (WA hat einen Fehler eingereicht) Der größte Feind war diesmal TLE. Ich habe kein Bild vom Rechenaufwand, aber ich kannte die interne Implementierung von Python nicht. Als ich mir das Problem ansah, hatte ich die Angewohnheit, das Problem zu sortieren, vorerst die Maximal- und Minimalwerte zu finden. Zuerst dachte ich, dass der Mindestwert herauskommen würde, wenn ich in der Reihenfolge mit for subtrahiere,

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)

Ich dachte, es würde funktionieren. Es ist jedoch notwendig, den Minimalwert unter k zu finden, der aus n ausgewählt ist. Daher ist es notwendig, k sortierte Eingänge und max-min unter ihnen herauszuziehen. Als ich darüber nachdachte, wie man k mal k nimmt, habe ich Slices verwendet, weil die Python-Liste Slices enthält. Das war ein großer Fehler. Anscheinend ** brauchen Python-Slices extrem viel Zeit, wenn sie auf großen Objekten ausgeführt werden **. Wenn Sie den Grund kennen, lassen Sie es mich bitte wissen. Dauert der Zugriff auf das Objekt sehr lange? Also derjenige, der TLE mit Scheiben verwendet

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] #Hier
    seed = min(high,seed)

print(seed)

Ich verbringe Zeit damit, den Kommentarteil aufzuschneiden. Selbst wenn ich meine, war tax_free, das ich in Scheiben schneiden möchte, viermal TLE. Wenn Sie jetzt darüber nachdenken, können Sie es nach Index angeben, ohne es separat zu schneiden.

Es stellte sich heraus, dass die Scheibe lange Zeit aß, also habe ich dies im Index angegeben

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)

Nicht in Scheiben geschnitten.

Zusammenfassung

Ich habe nicht verstanden, wie sich Python anfühlt. Geben Sie von nun an direkt nach Index an, ohne Slices zu verwenden. wir sehen uns