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

AtCoder ABC 030 A&B&C AtCoder - 030

Un problème

• Comme il est difficile de gérer la virgule décimale, passez à la multiplication
• {$ b \ div a <d \ div c } ou { b \ div a> d \ div c } -Changé en { b \ times c <d \ times a } ou { b \ times c> d \ times 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");
		}
	}

Problème B

--Mendoi calcule l'angle de l'aiguille des minutes de l'horloge

• Avec cette méthode de calcul, 23h59 est exact, mais à 23h10, il dépasse 180, donc soustrayez de `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 est supérieur à 180
		 */
		if (res > 180) {
			out.println(360 - res);
		} else {
			out.println(res);
		}
	}

Problème C: Dichotomie

--Utiliser la dichotomie

• Par la suite, boucle jusqu'à la fin de la recherche (l'acquisition d'index BinarySearch dépasse chaque index final)
• Obtenez le temps minimum que vous pouvez quitter l'aéroport avec la recherche binaire --Si vous pouvez effectuer une recherche, enregistrez le passage à l'heure actuelle + X
• Obtenez le temps minimum que vous pouvez quitter l'aéroport B avec la recherche binaire --Si vous pouvez rechercher, enregistrer l'heure actuelle + Y et déplacer
• Le nombre de fois où le nombre déplacé / 2 a fait un aller-retour ――Cependant, s'il s'agit d'un nombre pair, on peut considérer que vous pourriez faire un aller-retour, mais s'il s'agit d'un nombre impair, -1 puis /
• Pour éliminer le cas de déplacement uniquement vers X-> Y

	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) {
			/*
			 *Départ aéroport A ou départ B
			 */
			if (isAirportA) {
				/*
				 *Trouvez un vol à l'aéroport A qui peut décoller de l'heure actuelle
				 */
				int aI = Arrays.binarySearch(aA, currentTime);
				aI = aI >= 0 ? aI : ~aI;
				//Suite à une recherche de deux minutes, si vous atteignez la dernière position d'index, c'est déjà terminé
				if (aI >= n) {
					break;
				}
				/*
				 *Heure de départ du prochain aéroport B
				 */
				currentTime = aA[aI] + x;
				/*
				 *Le prochain est l'aéroport B
				 */
				isAirportA = false;
				moveCnt++;
			} else {
				/*
				 *Le contenu remplace simplement toutes les valeurs de l'aéroport A par B
				 */
				int bI = Arrays.binarySearch(bA, currentTime);
				bI = bI >= 0 ? bI : ~bI;
				if (bI >= m) {
					break;
				}
				currentTime = bA[bI] + y;
				isAirportA = true;
				moveCnt++;
			}
		}
		/*
		 *X lorsque le nombre de mouvements est impair->Je suis juste allé à Y
		 *Je n'ai pas pu faire un aller-retour.
		 *Par conséquent, le mouvement de cette époque est poire
		 */
		if ((moveCnt & 1) == 1) {
			moveCnt -= 1;
		}
		/*
		 *Le nombre de fois où la moitié du nombre de personnes dans l'avion pourrait faire un aller-retour
		 */
		out.println(moveCnt / 2);

	}

Problème C: Une autre solution (déterminée uniquement par pour, sans utiliser de dichotomie)

• O $ (2N) $? Montant du calcul

«J'ai pu trouver une dichotomie et l'implémenter immédiatement, mais c'est un peu sale, donc si je cherchais une autre méthode, je sentais que je pouvais l'implémenter ici aussi, alors je l'ai essayée. ―― Plutôt que de rechercher tous les $ A [i] et B [i] $ à chaque fois, si vous gardez l'index au milieu, pourquoi ne pas simplement tourner les deux tableaux une fois? L'idée

--Trouver l'heure de départ d'un aéroport

• Obtenez {$ heure de départ + X $} à l'aéroport A --Trouver l'heure de départ de l'aéroport B
• Obtenez {$ heure de départ + Y $} de l'aéroport B & (obtenez le prochain index de démarrage de la recherche et arrêtez la recherche par heure) --Trouver l'heure de départ d'un aéroport
• Obtenez {$ heure de départ + X $} à l'aéroport A --- La boucle suivante

	/*
	 *Recherche complète?
	 */
	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++) {
			//Les heures de départ inférieures à l'heure actuelle ne peuvent pas être utilisées
			if (currentTime > aA[i]) {
				continue;
			}
			//Peut partir d'un aéroport
			currentTime = aA[i] + x;
			//Commencez à chercher du temps à l'aéroport B
			for (int j = bI; j < m; j++) {
				//Les heures de départ inférieures à l'heure actuelle ne peuvent pas être utilisées
				if (currentTime > bA[j]) {
					continue;
				}
				/*
				 *Cette fois peut être utilisée, donc
				 *・ Réglez l'heure de départ du prochain aéroport A
				 *・ Définissez l'index pour démarrer la recherche horaire du prochain aéroport B
				 */
				currentTime = bA[j] + y;
				bI = j + 1;
				//J'ai pu quitter l'aéroport B donc j'ai pu faire un aller-retour
				moveCnt++;
				break;
			}
		}
		out.println(moveCnt);
	}