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

AtCoder ABC 030 A&B&C AtCoder - 030

Ein Problem

• Da es schwierig ist, mit dem Dezimalpunkt umzugehen, wechseln Sie zur Multiplikation
• {$ b \ div a <d \ div c } oder { b \ div a> d \ div c $}
• Geändert zu {$ b \ mal c <d \ mal a } oder { b \ mal c> d \ mal a $}

	private void solveA() {
		int a = nextInt();
		int b = nextInt();
		int c = nextInt();
		int d = nextInt();
		if (b * c > a * d) {
			out.println("TAKAHASHI");
		} else if (b * c < a * d) {
			out.println("AOKI");
		} else {
			out.println("DRAW");
		}
	}

B Problem

--Mendoi berechnet den Winkel des Stundenzeigers der Uhr

• Mit dieser Berechnungsmethode ist 23:59 genau, aber um 23:10 überschreitet sie 180, also subtrahieren Sie von "360".

	private void solveB() {
		int n = nextInt();
		int m = nextInt();

		double smallHand = n % 12 * 30 + m * 0.5;//n % 12 * (360 / 12) + m * (360 / 12 /  60)
		double longHand = m % 60 * 6;//m % 60 * (360 / 60)

		double res = Double.max(smallHand, longHand) - Double.min(smallHand, longHand);
		/*
		 * 23:10 ist größer als 180
		 */
		if (res > 180) {
			out.println(360 - res);
		} else {
			out.println(res);
		}
	}

Problem C: Dichotomie

• Verwenden Sie Dichotomie
• Danach Schleife bis zum Ende der Suche (BinarySearch-Indexerfassung überschreitet jeden endgültigen Index)
• Holen Sie sich die Mindestzeit, die Sie mit Binary Search den Flughafen verlassen können
• Wenn Sie suchen können, notieren Sie, dass Sie zur aktuellen Zeit + X verschoben wurden
• Holen Sie sich die Mindestzeit, die Sie Flughafen B mit Binary Search verlassen können
• Wenn Sie suchen können, zeichnen Sie die aktuelle Zeit + Y auf und bewegen Sie sich
• Die Häufigkeit, mit der die bewegte Zählung / 2 eine Rundreise durchgeführt hat ――Wenn es sich jedoch um eine gerade Zahl handelt, kann davon ausgegangen werden, dass eine Rundreise möglich war. Wenn es sich jedoch um eine ungerade Zahl handelt, ist dies -1 und dann / 2. --Um den Fall zu beseitigen, dass nur zu X-> Y gewechselt wird

	private void solveC2() {
		int n = nextInt();
		int m = nextInt();
		long x = nextInt();
		long y = nextInt();
		long[] aA = LongStream.range(0, n).map(i -> nextLong()).toArray();
		long[] bA = LongStream.range(0, m).map(i -> nextLong()).toArray();

		/*
		 * true = airport A
		 * false = airport B
		 */
		boolean isAirportA = true;
		long currentTime = 0;
		long moveCnt = 0;
		while (true) {
			/*
			 *Abflug vom Flughafen A oder Abflug vom Flughafen B.
			 */
			if (isAirportA) {
				/*
				 *Suchen Sie einen Flug am Flughafen A, der von der aktuellen Zeit abfliegen kann
				 */
				int aI = Arrays.binarySearch(aA, currentTime);
				aI = aI >= 0 ? aI : ~aI;
				//Wenn Sie nach zwei Minuten suchen und die letzte Indexposition erreichen, ist diese bereits beendet
				if (aI >= n) {
					break;
				}
				/*
				 *Zeit zum Abflug vom nächsten B-Flughafen
				 */
				currentTime = aA[aI] + x;
				/*
				 *Weiter ist B Flughafen
				 */
				isAirportA = false;
				moveCnt++;
			} else {
				/*
				 *Der Inhalt ersetzt lediglich alle Werte des Flughafens A durch B.
				 */
				int bI = Arrays.binarySearch(bA, currentTime);
				bI = bI >= 0 ? bI : ~bI;
				if (bI >= m) {
					break;
				}
				currentTime = bA[bI] + y;
				isAirportA = true;
				moveCnt++;
			}
		}
		/*
		 *X, wenn die Anzahl der Bewegungen ungerade ist->Ich bin gerade zu Y gegangen
		 *Ich konnte keine Rundreise machen.
		 *Daher ist die Bewegung dieser Zeit Birne
		 */
		if ((moveCnt & 1) == 1) {
			moveCnt -= 1;
		}
		/*
		 *Die Häufigkeit, mit der die Hälfte der Anzahl der Personen im Flugzeug eine Rundreise unternehmen konnte
		 */
		out.println(moveCnt / 2);

	}

Problem C: Eine andere Lösung (nur bestimmt durch für, ohne Dichotomie)

• $ O (2N) $? Berechnungsbetrag

――Ich konnte eine Dichotomie entwickeln und sie sofort implementieren, aber sie ist irgendwie schmutzig. Wenn ich also nach einer anderen Methode suchte, hatte ich das Gefühl, dass ich sie auch hier implementieren könnte, also habe ich es versucht. ―― Anstatt jedes Mal nach allen $ A [i] und B [i] $ zu suchen, sollten Sie beide Arrays einfach einmal drehen, wenn Sie den Index in der Mitte halten. Die Idee

--Finden Sie die Abflugzeit eines Flughafens

• Holen Sie sich {$ Abflugzeit + X $} an einem Flughafen
• Finden Sie die Abflugzeit des Flughafens B.
• Holen Sie sich {$ Abflugzeit + Y $} vom Flughafen B & (holen Sie sich den Startindex für die nächste Suche und stoppen Sie die Zeitsuche) --Finden Sie die Abflugzeit eines Flughafens
• Holen Sie sich {$ Abflugzeit + X $} an einem Flughafen --- Die folgende Schleife

	/*
	 *Volle Suche?
	 */
	private void solveC() {
		int n = nextInt();
		int m = nextInt();
		long x = nextInt();
		long y = nextInt();
		long[] aA = LongStream.range(0, n).map(i -> nextLong()).toArray();
		long[] bA = LongStream.range(0, m).map(i -> nextLong()).toArray();

		int bI = 0;
		long currentTime = 0;
		long moveCnt = 0;
		for (int i = 0; i < n; i++) {
			//Abfahrtszeiten, die kleiner als die aktuelle Zeit sind, können nicht verwendet werden
			if (currentTime > aA[i]) {
				continue;
			}
			//Kann von einem Flughafen abfliegen
			currentTime = aA[i] + x;
			//Beginnen Sie am Flughafen B nach Zeit zu suchen
			for (int j = bI; j < m; j++) {
				//Abfahrtszeiten, die kleiner als die aktuelle Zeit sind, können nicht verwendet werden
				if (currentTime > bA[j]) {
					continue;
				}
				/*
				 *Diese Zeit kann also genutzt werden
				 *・ Stellen Sie die Abflugzeit des nächsten A-Flughafens ein
				 *・ Legen Sie den Index für den Start der Zeitsuche für den nächsten B-Flughafen fest
				 */
				currentTime = bA[j] + y;
				bI = j + 1;
				//Ich konnte Flughafen B verlassen und eine Rundreise machen
				moveCnt++;
				break;
			}
		}
		out.println(moveCnt);
	}