2017-02-20 2 views
1

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.

+1

Denken Sie über die Gesamtsumme und über den maximalen Elementwert nach. – MBo

Antwort

1

Zuerst können Sie alle Werte zusammenfassen. Lass uns diesen MAX nennen. Dann überprüfen Sie, ob es ein einzelnes Element gibt, das mehr als MAX/2 enthält, nennen wir dieses Element BIG. Wenn diese Bedingung nicht erfüllt ist, sollte die Antwort einfach MAX/2 lauten. Wenn diese Bedingung jedoch erfüllt ist, müssen wir 1 von BIG und von MAX subtrahieren, bis BIG kleiner oder gleich MAX/2 ist.

+0

Wir müssen auch annehmen, dass MAX auch dann ist, wenn es nicht ist, dann subtrahieren wir einfach 1, bevor wir mit dem Verfahren beginnen. –

+1

Können Sie bitte erklären, warum das funktioniert? – cryptomanic

+0

Wenn Sie den Ansatz verwenden, um immer die zwei höchsten Werte auszuwählen, erhalten Sie die optimale Summe. und du subtrahierst 2 von MAX jedes Mal, wenn du 1 zu den Gesamtpunkten hinzufügst. Das einzige Problem, das auftreten kann, ist, wenn der höchste Wert nicht vollständig reduziert werden kann oder MAX ungerade ist. Tut mir leid, ich weiß nicht, wie ich das besser erklären soll. –

Verwandte Themen