Daily AtCoder # 3 en Python

introduction

Dernière fois C'est le troisième jour.

** Pensées ** 1WA, 4TLE (WA a soumis une erreur) Le plus grand ennemi cette fois était TLE. Je n'ai pas d'image de la quantité de calcul, mais je ne connaissais pas l'implémentation interne de Python. En regardant le problème, j'ai pris l'habitude de trier le problème de trouver les valeurs maximales et minimales pour le moment. Au début, je pensais que la valeur minimum sortirait si je soustrais dans l'ordre avec pour,

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)

Je pensais que cela fonctionnerait avec. Cependant, il est nécessaire de trouver la valeur minimale parmi k choisis parmi n. Par conséquent, il est nécessaire de retirer k entrées triées et max-min parmi elles. Quand j'ai réfléchi à la façon de prendre k par k, j'ai utilisé des tranches car la liste Python a des tranches. C'était une grosse erreur. Apparemment ** les tranches Python prennent ultra-temps lorsqu'elles sont effectuées sur de gros objets **. Si vous connaissez la raison, faites-le moi savoir. Est-ce que cela prend beaucoup de temps pour accéder à l'objet? Donc, celui qui TLE utilise des tranches

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

print(seed)

Je passe du temps à découper la partie commentaire. Même si je veux dire, tax_free que je veux couper a été TLE quatre fois. Si vous y réfléchissez maintenant, vous pouvez le spécifier par index sans le découper séparément.

Il s'est avéré que la tranche mangeait depuis longtemps, c'est donc ce que j'ai spécifié dans l'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)

Pas tranché.

Résumé

Je n'ai pas compris ce que ressent Python. Désormais, spécifiez directement par index sans utiliser de tranches. à plus