[JAVA] ABC - 022 - A & B & C.

AtCoder ABC 022 A&B&C AtCoder - 022

** 14.05.2019 Nachschrift ** Problem B: Codeänderung, um die Summe der res zu erhalten

Ein Problem

--Überprüfen Sie, ob das Gewicht bei jeder Aufnahme im richtigen Bereich liegt

	private void solveA() {
		int n = nextInt();
		int s = nextInt();
		int t = nextInt();
		int w = nextInt();

		long sum = w;
		int res = 0;
		for (int i = 0; i < n; i++) {
			if (i != 0) {
				sum += nextInt();
			}
			if (s <= sum && sum <= t) {
				res++;
			}
		}

		out.println(res);
	}

B Problem

(2019/05/14 Codekorrektur, um die Summe der Res zu erhalten)

• Sie können Folgendes sehen, indem Sie die Problemstellung lesen

• Kann nicht verschmutzen, wenn es nur eine Blume eines bestimmten Typs gibt

• Zwei oder mehr Blüten sind n-1 verschmutzt

• Drei Blumen verschmutzen zwei

• Zählen Sie zwei oder mehr Blumen

• Jede Blume ist n-1 verschmutzt, also zählen

• Der auskommentierte Teil funktioniert auch. Einige Versuche, um das Schreiben zu bestätigen

		int numN = nextInt();

		Map<Integer, Long> tmp = IntStream.range(0, numN).map(i -> nextInt()).mapToObj(i -> new Integer(i))
				.collect(Collectors.groupingBy(s -> s, Collectors.counting()));

		long res = tmp.values().stream().mapToLong(i -> i - 1).sum();

		//		long res = tmp.values().stream().filter(i -> i.longValue() > 1).reduce(0L, (sum, i) -> sum += (i - 1));

		//		int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();
		//		Map<Integer, Long> tmp = Arrays.stream(wk).mapToObj(i -> new Integer(i))
		//				.collect(Collectors.groupingBy(s -> s, Collectors.counting()));
		//		long res = tmp.values().stream().filter(i -> i.longValue() > 1).reduce(0L, (sum, i) -> sum += (i - 1));

		out.println(res);

Problem C: Worshall Floyd-Methode

――Gehen Sie aus 1 heraus und kehren Sie zu 1 zurück ――Jedoch können Sie nicht dieselbe Straße benutzen

• Die Eckpunkte neben 1 müssen auf den ausgehenden und eingehenden Fahrten geändert werden -Finden Sie den kürzesten Weg zwischen den Eckpunkten neben 1 und berechnen Sie die folgenden Bewegungskosten --1-> Benachbarte Eckpunkte 1-> Benachbarte Eckpunkte 2-> 1

• Runde für benachbarte Eckpunkte 1-2

• Verwenden Sie die ** Worshall Floyd-Methode **, um [benachbarte Eckpunkte 1-> benachbarte Eckpunkte 2] zu berechnen.

• Bei der Berechnung von [Benachbarte Scheitelpunkte 1-> Benachbarte Scheitelpunkte 2] habe ich eine benachbarte Matrix erstellt, die die Kosten von 1 weglässt, und diese berechnet, da sie zweimal über [1] dieselbe Stelle durchläuft.

• Berechnungsergebnis von graphWithOutStart basierend auf Beispiel 1 (Berechnungsergebnis der benachbarten Matrix 鵜 ohne Scheitelpunkt 1)

• Alle sind tINF, weil sie nicht durch Scheitelpunkt 1 gehen.

• Zum Vergleich: Diagrammberechnungsergebnis basierend auf Beispiel 1 (Ergebnis der Mindestkostenberechnung für jeden Scheitelpunkt)

	private void solveC() {
		final long CONST_INF = Long.MAX_VALUE / 10;

		int n = nextInt();
		int m = nextInt();
		long[][] graphWithOutStart = new long[n][n];
		long[][] graph = new long[n][n];
		List<Integer> edgeNearByStart = new ArrayList<Integer>();

		/*
		 *Graphinitialisierung
		 * [1]Mit benachbarter Matrix inklusive[1]Erstellen einer benachbarten Matrix ohne
		 */
		for (int i = 0; i < n; i++) {
			Arrays.fill(graph[i], CONST_INF);
			Arrays.fill(graphWithOutStart[i], CONST_INF);
			graphWithOutStart[i][i] = 0;
			graph[i][i] = 0;
		}

		for (int i = 0; i < m; i++) {

			/*
			 *Nach dem Index-1 und erfassen
			 */
			int from = nextInt() - 1;
			int to = nextInt() - 1;
			int cost = nextInt();
			if (from != 0) {
				/*
				 * [1]Grafik ohne
				 */
				graphWithOutStart[from][to] = cost;
				graphWithOutStart[to][from] = cost;
			} else {
				/*
				 * [1]Angrenzend an die Eckpunkte
				 */
				edgeNearByStart.add(to);
			}
			graph[from][to] = cost;
			graph[to][from] = cost;
		}

		long res = Long.MAX_VALUE;

		Collections.sort(edgeNearByStart);

		/*
		 *Warshall - Floyd-Methode zum Aktualisieren von Scheitelpunkten
		 */

		getMinByWarshall(graphWithOutStart, n);

		for (int i = 0; i < edgeNearByStart.size(); i++) {
			for (int j = i + 1; j < edgeNearByStart.size(); j++) {
				int start = edgeNearByStart.get(i);
				int end = edgeNearByStart.get(j);
				/*
				 * [1]Von[Benachbarte Eckpunkte 1]Kosten+ [Benachbarte Eckpunkte 1][Benachbarte Eckpunkte 2]Kosten+ [Benachbarte Eckpunkte 2]Von[1]Kosten
				 */
				long total = graph[0][start] + graphWithOutStart[start][end] + graph[0][end];
				//Niedrigen Wert annehmen
				res = Long.min(res, total);
			}

		}

		out.println(res >= CONST_INF ? -1 : res);

	}

	/**
	 *
	 * @param edge
	 * @param point
	 */
	private void getMinByWarshall(long[][] edge, int point) {
		for (int k = 0; k < point; k++) {
			for (int i = 0; i < point; i++) {
				for (int j = 0; j < point; j++) {
					edge[i][j] = Long.min(edge[i][j], edge[i][k] + edge[k][j]);
				}
			}
		}

	}

Problem C: Worshall Floyd-Methode (Kurzcode-Version)

• Bei der Berechnung von [Benachbarte Scheitelpunkte 1-> Benachbarte Scheitelpunkte 2] habe ich eine benachbarte Matrix erstellt, bei der die Kosten von 1 weggelassen werden, da sie über [1] zweimal dieselbe Stelle durchläuft. Wenn Sie den Index von [1] anstelle von [0] starten, können Sie die Kosten berechnen, ohne [Peak 1] zu durchlaufen. .. ..
• Auf diese Weise können Sie mit der Worshall Floyd-Methode rechnen, ohne eine benachbarte Matrix zu erstellen, bei der Scheitelpunkt 1 weggelassen wird. Dies beschleunigt und ist leicht zu erkennen.

• Die folgende Tabelle zeigt die Ergebnisse, die nach der Warshall Floyd-Methode aus dem Index [1] mit Beispiel 1 berechnet wurden.
• Die Kosten für die Verschiebung zu 1 werden für die Eckpunkte (2,4,5) neben 1 berechnet, die Kosten werden jedoch nicht für die Eckpunkte (3) berechnet, die nicht neben 1 liegen.
• Die Mindestkosten von Scheitelpunkt 2 zu Scheitelpunkt 4 betragen 3, aber das berechnete Ergebnis sind die Kosten für das Verschieben des Scheitelpunkts [2-> 5-> 3-> 4] auf 10.

• Zum Vergleich: Bei Berechnung aus Index [1] und bei Berechnung aus Index [0]
• Die folgende Tabelle berechnet die benachbarte Matrix ohne Scheitelpunkt 1 aus dem Index [0].

	private void solveC() {
		final long CONST_INF = Long.MAX_VALUE / 10;

		int n = nextInt();
		int m = nextInt();
		long[][] graph = new long[n][n];

		/*
		 *Graphinitialisierung
		 * [1]Mit benachbarter Matrix inklusive[1]Erstellen einer benachbarten Matrix ohne
		 */
		for (int i = 0; i < n; i++) {
			Arrays.fill(graph[i], CONST_INF);
			graph[i][i] = 0;
		}

		for (int i = 0; i < m; i++) {

			/*
			 *Nach dem Index-1 und erfassen
			 */
			int from = nextInt() - 1;
			int to = nextInt() - 1;
			int cost = nextInt();
			graph[from][to] = cost;
			graph[to][from] = cost;
		}

		long res = Long.MAX_VALUE;

		/*
		 *Warshall - Floyd-Methode zum Aktualisieren von Scheitelpunkten
		 */

		/*
		 *Wenn Sie den Index mit 1 starten, wird er für 1 nicht aktualisiert
		 */
		for (int k = 1; k < n; k++) {
			for (int i = 1; i < n; i++) {
				for (int j = 1; j < n; j++) {
					graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
				}
			}
		}

		for (int i = 1; i < n; i++) {
			for (int j = 1; j < n; j++) {
				if (i != j) {
					res = Math.min(res, graph[0][i] + graph[i][j] + graph[j][0]);
				}
			}
		}

		out.println(res >= CONST_INF ? -1 : res);

	}