Einführung in Algorithmen mit der Java-Shakutori-Methode

Artikelübersicht

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

In diesem Artikel

• • Shakutori-Methode *

Ich werde darüber lernen. Mit kumulierter Summe? Wird es verwendet? Ich sehe sie oft als Set vorgestellt.

Shakutori-Methode

Wie die kumulative Summe scheint es eine Technik zu sein, Operationen auf einem Array von Zahlen zu beschleunigen.

Referenz: [[Kumulative Summe, Shakutori-Methode] Algorithmus-Illustration, die selbst Anfänger verstehen können](https://paiza.hatenablog.com/entry/2015/01/21/%E3%80%90%E7%B4%AF% E7% A9% 8D% E5% 92% 8C% E3% 80% 81% E3% 81% 97% E3% 82% 83% E3% 81% 8F% E3% 81% A8% E3% 82% 8A% E6% B3% 95% E3% 80% 91% E5% 88% 9D% E7% B4% 9A% E8% 80% 85% E3% 81% A7% E3% 82% 82% E8% A7% A3% E3% 82% 8B% E3% 82% A2% E3% 83% AB% E3% 82% B4)

Nun ... es ist ein bisschen verwirrend, wenn Sie sich den Link ansehen. .. .. Ich werde es für mein eigenes Studium erklären.

Betrachten Sie als Beispiel ein ganzzahliges Array der Größe n. Was ist der Maximalwert der Summe innerhalb dieses Abschnitts, wenn er von dort in die Länge t des angegebenen Abschnitts unterteilt wird? Es ist ein Problem, ein typisches Problem zu lösen. Es ist ein Problem, das mit der kumulierten Summe gelöst werden kann. Siehe auch den vorherigen Artikel (https://qiita.com/aja_min/items/3a334fb03749d8f42a25).

Betrachten Sie als Beispiel den Fall der Größe 5 (n = 5) und der Intervalllänge 2 (t = 2).

Betrachten Sie die Anordnung wie gezeigt. Wenn Sie dies durch die Länge von 2 des Abschnitts teilen, ist dies wie folgt.

Aus der Schlussfolgerung ist 4 + 10 = 14 der Summe bei Auswahl des 4. und 5. der höchste Wert, aber wie hoch ist der Berechnungsbetrag bisher?

1. Welchen Abschnitt auswählen?
2. Berechnung der Summe innerhalb des Intervalls

Lassen Sie uns separat darüber nachdenken.

Zunächst einmal: 1. Wie teilt man den Abschnitt, nicht wahr? Im obigen Beispiel wird die Summe viermal genommen. Wenn Sie es in die Formel einfügen, ist es n-t + 1 Mal. Diesmal 5-2 + 1 = 4 mal.

Als nächstes folgt 2. Berechnung der Summe innerhalb dieses Intervalls, die zweimal verarbeitet wird, um auf jedes Element des Arrays zuzugreifen.

Im Allgemeinen ist es (n - t + 1) * t mal. Beachten Sie, dass, wenn t von n abhängt, der Berechnungsbetrag ungefähr O (n ^ 2) beträgt. In diesem Fall dauert es enorm lange, wenn n als 10 ^ 5 angenommen wird. In einem solchen Fall wird die Shakutori-Methode eingeführt.

Nun, es ist eine relativ einfache Geschichte ... Merken Sie sich die Summe, damit Sie nicht jedes Mal 1 hinzufügen müssen. darüber. Siehe die Abbildung unten.

Verstehst du irgendwie Wenn Sie sich an die Summe erinnern, müssen Sie nicht alle Elemente t-mal gleichzeitig hinzufügen. Der Rechenaufwand beträgt n-t + 1-mal, da nicht mehr auf jedes Element des Arrays zugegriffen werden muss. Ich denke, es kann als O (n) ausgedrückt werden.

Gehen wir zum Beispiel.

Beispiel

Beispiel: AtCoder --abc032-c "column"

N K
s1 
s2
:
sN

Das ist das Problem. Es ist ein wenig angewendet. Es ist im Grunde eine wackelige Methode, aber diesmal ist die Länge noch nicht festgelegt. Es wird gemäß der folgenden Richtlinie implementiert.

• Speichern Sie das Produkt auf die gleiche Weise wie bei der Shakutori-Methode.
• Solange die Bedingungen erfüllt sind, fahren Sie mit dem rechten Ende fort.
• Wenn die Bedingungen nicht mehr erfüllt sind, fahren Sie mit dem linken Ende fort. ――Wenn das linke Ende ganz rechts liegt, endet die Suche. Der zu diesem Zeitpunkt längste Wert wird ausgegeben.

Unten finden Sie eine Beispielantwort.

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(); //Nicht negative Ganzzahlzeichenfolgenlänge
		long k = sc.nextLong(); //Maximales Produkt

		long[] s = new long[n]; //Nicht negative Ganzzahlzeichenfolge

		for (int i = 0; i < n; i++) {
			s[i] = sc.nextLong();
			if (s[i] == 0l) {
				System.out.println(n);
				return;
			}
		}

		long seki = 1; //Variablen, die das Produkt speichern
		int ans = 0; //Maximale Länge
		int ans_max = -1; //Speichern Sie die Antwort
		int left = 0; //Linkes Ende
		int right = 0; //Rechtes Ende

		for (left = 0; left < n; left++) {

			//Befestigen Sie das linke Ende und bewegen Sie das rechte Ende so weit wie möglich, um zu multiplizieren
			while (right < n && seki * s[right] <= k) {
				seki *= s[right++];
			}

			//Lagerung von maximal ans
			ans = right - left;
			if (ans_max < ans) {
				ans_max = ans;
			}

			//Bewegen Sie den linken Rand. links==Sei vorsichtig, wenn es richtig wird.
			if (left == right) {
				right++;
			} else {
				seki /= s[left];
			}

		}

		System.out.println(ans_max);
	}
}

Ja. Ich bezog mich auf verschiedene Quellen, aber es war ziemlich schwierig. .. Das Beispiel, in dem links mit rechts aufholt, war besonders schwierig. Dies scheint auch Übung zu erfordern. .. .. Lass uns gut üben. Ich werde die Quelle immer und immer wieder lesen.

wir sehen uns!