Einführung in Algorithmen mit Java-kumulativer Summe

Artikelübersicht

Dies ist eine Reihe von Artikeln, die ich in meiner Studie und meinem Memo zusammengestellt habe. Der fünfte. Klicken Sie hier für vorherige Artikel.

In diesem Artikel

• ** Kumulative Summe **

Ich werde darüber lernen. Lassen Sie uns den Erkundungsabschnitt beenden und einen anderen Algorithmus untersuchen (was Sie am wöchentlichen Wettbewerb interessiert hat).

Kumulative Summe

Es scheint eine Berechnungstechnik zu sein. Es scheint zweckmäßig zu sein, die Summe der Abschnitte mit dem Array zu finden.

Referenz: Schreiben Sie die kumulative Summe ohne nachzudenken!

Ich werde es vorerst erklären.

Sequenz a, {1,3,1,4,7,6,1,0,9} Sollen wir das sagen? Angenommen, Sie werden aufgefordert, die Summe aus dem 3. bis 5. dieser Sequenz zu ermitteln.

Normale Methode

a: Addiere einfach den 3. bis 5. von {1,3, ** 1,4,7 **, 6,1,0,9}. Die Antwort lautet 1 + 4 + 7 = 12

Verwenden Sie die kumulative Summe

Erstellen Sie zusätzlich zu a ein Array b, in dem die Summe bis zum i-ten von a gespeichert ist. b：{0,1,4,5,9,16,22,23,23,32} Wenn Sie a_1 wie das erste Element von a schreiben, b_1 = 0 (hier behoben. Indizes werden danach um eins verschoben) b_2 = a_1 = 1 b_3 = a_1 + a_2 = 1 + 3 = 4 b_4 = a_1 + a_2 + a_3 = 1 + 3 + 1 = 5 b_5 = a_1 + ... + a_4 = 1 + ... + 4 = 9 b_6 = a_1 + ... + a_5 = 1 + ... + 7 = 16 ...

Ich fühle mich gesagt. Zu diesem Zeitpunkt wird die Summe des 3. bis 5. von a wie folgt berechnet. b_6 - b_3 = 16 - 4 = 12

Die Einzelheiten sind wie folgt.

  b_6 = a_1 + a_2 + a_3 + a_4 + a_5
-)b_3 = a_1 + a_2
--------------------------------------
      = a_3 + a_4 + a_5

Verstehst du irgendwie Wenn Sie die Summe in der Reihenfolge von vorne speichern, müssen Sie sich nicht die Mühe machen, 3. + 4. + 5. hinzuzufügen!

Worüber freust du dich?

Wenn Sie beispielsweise die Summe von ● bis ▲ mehrmals ermitteln müssen (unter der Annahme eines Problems mit vielen Variationen von ● und ▲), müssen Sie die Schleife auf die übliche Weise immer wieder drehen. Es gibt, aber wenn Sie die kumulative Summe verwenden, können Sie die Gesamtsumme (mit O (1)) in einem Schuss finden.

Schauen wir uns das Problem an.

Beispiel

Beispiel: AtCoder --abc037-c "total"

N K
a1 .. aN

Das ist das Problem. Es ist nur eine Frage der kumulierten Summe. Sie müssen K-Stücke N-K + 1 Mal hinzufügen. Der Berechnungsbetrag beträgt O (K * (N-K + 1)). Wenn Sie eine schlechte Wahl treffen (K = N / 2 usw.), werden Sie feststellen, dass dies O (N ^ 2) kostet. Dies ist nicht rechtzeitig. Deshalb kommt die kumulative Summe ins Spiel. "K-Additionen sind N-K + 1-mal", aber wenn Sie die kumulative Summe verwenden, können "K-Additionen" alle mit O (1) durchgeführt werden, sodass der Berechnungsbetrag ungefähr O (N) beträgt. ..

Die Richtlinie lautet wie folgt.

• Bereiten Sie ein Array für die kumulative Summe vor
• Die Summe von 1 ~ K, 2 ~ K + 1,3 ~ K + 2, ..., N-K + 1 ~ N wird durch die Folge der kumulativen Summen berechnet, und schließlich ist die Summe die Antwort.

Das Folgende ist ein Beispiel für die Antwort.

Main.java

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int k = sc.nextInt();

		long a[] = new long[n]; //Array zum Empfangen von Eingaben
		long b[] = new long[n + 1]; //Kumulative Summe speichern

		for (int i = 0; i < n; i++) {
			//Eingaben empfangen
			a[i] = sc.nextLong();
		}

		for (int i = 1; i <= n; i++) {
			//Kumulative Summenberechnung
			b[i] = b[i - 1] + a[i - 1];
		}

		long ans = 0; //Antwortspeicher
		for (int i = 0; i < n - k + 1; i++) {
			ans += b[i + k] - b[i];
		}

		System.out.println(ans);
	}
}

... Hmm, es war schwierig im Index. .. Insbesondere ist es schwierig, es ganz am Anfang der kumulierten Summe auf 0 zu setzen.

Gibt es nur wenig Übung? Ich bin froh, dass ich das Konzept und die Denkweise selbst kannte. Vorerst werde ich hier enden. Na dann ~.