[GO] Mémo d'apprentissage de la planification des sections ~ par python ~
introduction
Mémo d'apprentissage sur le problème de planification de section de méthode gloutonne
problème
Concours de programmation Keyence 2020 "Bras de robot à problème B"
Le problème de la sélection du plus grand nombre possible pour ceux qui ont des points de départ et d'arrivée fixes (problème d'ordonnancement de section) Résoudre avec une méthode gourmande La politique de base est de sélectionner le robot avec le plus petit point final parmi les robots qui peuvent être sélectionnés.
Répondre
N=int(input())
XL=[list(map(int,input().split())) for i in range(N)]
R=[]
for i in range(N):
a=max(0,XL[i][0]-XL[i][1])
b=XL[i][1]+XL[i][0]
R.append([b,a])
R.sort()
ans=0
con_l=0
for i in range(N):
if con_l <= R[i][1]:
ans += 1
con_l = R[i][0]
print(ans)
Commentaire
① Entrée
N=int(input())
XL=[list(map(int,input().split())) for i in range(N)]
N est le nombre de robots XL est une liste de coordonnées X et de longueur de bras L
② Modifier la liste
Créez une liste (R) pour stocker le point de départ (a) et le point final (b) du bras du robot
R=[]
for i in range(N):
a=max(0,XL[i][0]-XL[i][1])
b=XL[i][1]+XL[i][0]
R.append([b,a])
R.sort()
La liste R est triée par ordre croissant des points finaux
③ Planification et sortie des sections
ans=0
con_l=0
for i in range(N):
if con_l <= R[i][1]:
ans += 1
con_l = R[i][0]
print(ans)
ans est le nombre de robots sélectionnés con_l est le point final du bras du dernier robot sélectionné
Le traitement dans la boucle for est conçu pour rechercher avidement un robot avec un point de départ (R [i] [1]) plus grand que le point final (con_l) du dernier robot sélectionné. Puisque R est trié par ordre croissant des points finaux, celui avec le plus petit point final est toujours sélectionné lors de la recherche. Mettez à jour con_l en ajoutant +1 à ans à chaque fois qu'il est trouvé Sortie et finition
Résumé
C'était un problème typique de planification d'intervalle
Recommended Posts