Gegeben ein Array A [1: N]. Jedes Element des Arrays ist nicht negativ. Operation erlaubt: Wähle zwei Elemente des Arrays (der Wert beider Elemente muss mindestens 1 sein) und reduziere beide Elemente um 1. Auf diese Weise erhalten wir 1 Punkt. Was sind die maximalen Punkte, die verdient werden können?Wie maximiere ich die Gesamtpunkte?
Beispiel:
A[1:3] = 1 1 2
After step 1: 0 1 1
After step 2: 0 0 0
Maximum points = 2
Brute-Force-Ansatz:
total_points <- 0
while value of atleast two elements of A is greater than 0:
subtract 1 from both
total_points <- total_points + 1
return total_points
Wie die Annäherung verbessern? Bitte helfen Sie.
Denken Sie über die Gesamtsumme und über den maximalen Elementwert nach. – MBo