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

AtCoder ABC 127 A&B&C&D AtCoder - 127

Je serai de retour pour résoudre E & F dans un proche avenir.

2019/05/27 Correction du code B

A - Ferris Wheel

	private void solveA() {
		int a = nextInt();
		int b = nextInt();

		if (a <= 5) {
			out.println(0);
		} else if (a <= 12) {
			out.println(b / 2);
		} else {
			out.println(b);
		}
	}

B - Algae

• x_{2001}=r \times x_{2000}−D
• x_{2002}=r \times x_{2001}−D
• ・
• ・
• x_{i+1}=r \times x_i−D

	private void solveB() {
		int r = nextInt();
		int d = nextInt();
		int x2000 = nextInt();

		int pre = x2000;
		for (int i = 1; i <= 10; i++) {
			pre = r * pre - d;
			out.println(pre);
		}

	}

C - Prison

• Exemple d'entrée 1

4 2 1 3 2 4

--La première porte s'ouvre avec les touches 1,2,3 --La deuxième porte s'ouvre avec les clés 2, 3 et 4

• Quelques clés peuvent ouvrir les deux portes --Trouvez la clé utilisée dans toutes les portes

Je l'ai remplacé par un numéro.

Une clé avec total = nombre de portes peut ouvrir toutes les portes. Pour le traitement tel que l'ajout d'une certaine plage à une certaine plage, la méthode Imos est plus rapide.

Je publierai donc la liste habituelle des sites de référence

--Site de référence (méthode Imos et somme cumulée)

• Imosho
• Résumé de la méthode imos et du problème des sommes cumulées dans la programmation compétitive
• Etre capable d'écrire la somme cumulée sans réfléchir!

		int n = nextInt();
		int m = nextInt();

		//Pour mémo quelle touche numérique est requise à chaque porte
		int[] wk = new int[n];

		for (int i = 0; i < m; i++) {
			int l = nextInt() - 1;
			int r = nextInt() - 1;
			wk[l] += 1;
			if (r + 1 < n) {
				wk[r + 1] -= 1;
			}
		}

		//
		for (int i = 1; i < n; i++) {
			wk[i] += wk[i - 1];
		}
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			if (wk[i] == m) {
				cnt++;
			}
		}

		out.println(cnt);

D - Integer Cards

• Puisque l'ordre de réécriture des cartes n'est pas spécifié ――Il semble bon de réécrire les petites des cartes importées avec les grandes.

1. Disposer A (cartes prises) (ici par ordre croissant)
2. Organisez B (nombre de feuilles) et C (entier) dans l'ordre C (ordre décroissant ici)
3. Comparez avec [B, C] dans l'ordre croissant de A
4. Comparez jusqu'à B feuilles pour voir si C est plus grand que A, et réécrivez A si C est plus grand
5. Répétez 3-4

--Pour la 3ème partie, le traitement suivant est effectué dans le code, mais c'est parce que "B et C sont disposés dans l'ordre décroissant, donc la partie une fois réécrite avec C ne sera pas réécrite après cela (une fois réécrite C plus grand que C n'apparaît pas) " ――Si vous ne le faites pas, vous manquerez de temps en raison d'un traitement supplémentaire.

 //Il ne sert à rien de réécrire (comparer) au même endroit, alors décalez le début
        int start = 0;

--Code complet

	private void solveD() {
		int n = nextInt();
		int m = nextInt();
		long[] a = LongStream.range(0, n).map(i -> nextLong()).toArray();

		//Trier par ordre croissant
		Arrays.sort(a);

		int[][] bc = IntStream.range(0, m).collect(() -> new int[m][2],
				(t, i) -> {
					t[i][0] = nextInt();
					t[i][1] = nextInt();
				},
				(t, u) -> {
					Stream.concat(Arrays.stream(t), Arrays.stream(u));
				});

		//Trier par ordre décroissant de C
		Arrays.sort(bc, (x, y) -> -Integer.compare(x[1], y[1]));
		//Il ne sert à rien de réécrire (comparer) au même endroit, alors décalez le début
		int start = 0;
		for (int j = 0; j < m; j++) {
			int max = Integer.min((start + bc[j][0]), n);
			for (int k = start; k < max; k++) {
				if (bc[j][1] > a[k]) {
					//a[i]Est plus petit est réécrit
					a[k] = bc[j][1];
					//Se préparer à décaler le prochain départ
					start = k + 1;
				} else {
					//Déjà trié, donc un[i]Plus besoin de comparer si c'est plus gros
					break;
				}
			}

		}
		//total
		long res = Arrays.stream(a).sum();

		out.println(res);
	}