[GO] Abschnittsplanung Lernnotiz ~ von Python ~
Einführung
Lernnotiz über das Planungsproblem des gierigen Methodenabschnitts
Problem
"B Problem Robot Arms" von Keyence Programming Contest 2020
Das Problem, so viele wie möglich für diejenigen mit festen Start- und Endpunkten auszuwählen (Abschnittsplanungsproblem) Löse mit gieriger Methode Die grundlegende Richtlinie besteht darin, den Roboter mit dem kleinsten Endpunkt unter den Robotern auszuwählen, die ausgewählt werden können.
Antworten
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)
Kommentar
① Eingabe
N=int(input())
XL=[list(map(int,input().split())) for i in range(N)]
N ist die Anzahl der Roboter XL ist eine Liste der Koordinaten X und Armlänge L.
② Bearbeiten Sie die Liste
Erstellen Sie eine Liste (R), um den Startpunkt (a) und den Endpunkt (b) des Roboterarms zu speichern
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()
Liste R ist in aufsteigender Reihenfolge der Endpunkte sortiert
③ Abschnittsplanung und Ausgabe
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 ist die Anzahl der ausgewählten Roboter con_l ist der Endpunkt des zuletzt ausgewählten Roboterarms
Die Verarbeitung in der for-Schleife dient dazu, gierig nach einem Roboter zu suchen, dessen Startpunkt (R [i] [1]) größer ist als der Endpunkt (con_l) des zuletzt ausgewählten Roboters. Da R in aufsteigender Reihenfolge der Endpunkte sortiert ist, wird bei der Suche immer der mit dem kleinsten Endpunkt ausgewählt. Aktualisieren Sie con_l, indem Sie jedes Mal, wenn es gefunden wird, +1 zu ans hinzufügen Ausgabe und Ende
Zusammenfassung
Es war ein typisches Intervallplanungsproblem
Recommended Posts