AtCoder ABC 022 A&B&C AtCoder - 022
** PostScript 2019/05/14 ** Problème B: modification du code pour obtenir le total de res
--Vérifiez si le poids est dans la plage appropriée pour chaque prise
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);
}
(2019/05/14 Correction de code pour obtenir le total de res)
Vous pouvez voir ce qui suit en lisant l'énoncé du problème
Ne peut pas polluer lorsqu'il n'y a qu'une seule fleur d'un certain type --Deux fleurs ou plus sont polluées n-1 -Trois fleurs polluent deux
Comptez deux fleurs ou plus --Chaque fleur est polluée n-1, alors comptez
La partie commentée fonctionne également. Quelques essais pour confirmer comment écrire
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);
―― Sortez de 1 et revenez à 1 ――Cependant, vous ne pouvez pas emprunter la même route
--Résultat du calcul de graphWithOutStart basé sur l'exemple 1 (résultat du calcul de la matrice adjacente 鵜 à l'exclusion du sommet 1) --Tous sont des tINF car ils ne passent pas par le sommet 1.
| Pic 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | INF | INF | INF | INF |
| 2 | INF | 0 | 5 | 10 | 3 |
| 3 | INF | 5 | 0 | 5 | 2 |
| 4 | INF | 10 | 5 | 0 | 7 |
| 5 | INF | 3 | 2 | 7 | 0 |
--Pour comparaison: résultat du calcul du graphique basé sur l'exemple 1 (résultat du calcul du coût minimum pour chaque sommet)
| Pic 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| Pic 1 | 0 | 2 | 6 | 1 | 5 |
| 2 | 2 | 0 | 5 | 3 | 3 |
| 3 | 6 | 5 | 0 | 5 | 2 |
| 4 | 1 | 3 | 5 | 0 | 6 |
| 5 | 5 | 3 | 2 | 6 | 0 |
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>();
/*
*initialisation du graphe
* [1]Avec matrice adjacente comprenant[1]Créer une matrice adjacente sans
*/
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++) {
/*
*Selon l'indice-1 et capturer
*/
int from = nextInt() - 1;
int to = nextInt() - 1;
int cost = nextInt();
if (from != 0) {
/*
* [1]Graphique excluant
*/
graphWithOutStart[from][to] = cost;
graphWithOutStart[to][from] = cost;
} else {
/*
* [1]Adjacent aux sommets
*/
edgeNearByStart.add(to);
}
graph[from][to] = cost;
graph[to][from] = cost;
}
long res = Long.MAX_VALUE;
Collections.sort(edgeNearByStart);
/*
*Warshall - Méthode Floyd pour mettre à jour les sommets
*/
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]De[Sommets adjacents 1]Coût+ [Sommets adjacents 1][Sommets adjacents 2]Coût+ [Sommets adjacents 2]De[1]Coût
*/
long total = graph[0][start] + graphWithOutStart[start][end] + graph[0][end];
//Adoptez une faible valeur
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]);
}
}
}
}
-Lors du calcul des [sommets adjacents 1-> sommets adjacents 2], j'ai créé une matrice adjacente qui omet le coût de 1 car elle passe deux fois par le même endroit via [1]. Si vous démarrez l'indice de [1] au lieu de [0], vous pouvez calculer le coût sans passer par [Peak 1]. .. .. ――En utilisant cela, vous pouvez calculer par la méthode Worshall Floyd sans créer une matrice adjacente qui omet le sommet 1, ce qui accélère et est facile à voir.
| Pic 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| Pic 1 | 0 | 2 | INF | 1 | 12 |
| 2 | 2 | 0 | 5 | 10 | 3 |
| 3 | INF | 5 | 0 | 5 | 2 |
| 4 | 1 | 10 | 5 | 0 | 7 |
| 5 | 12 | 3 | 2 | 7 | 0 |
--Pour comparaison: calculé à partir de l'indice [1] et calculé à partir de l'indice [0]
| Pic 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | INF | INF | INF | INF |
| 2 | INF | 0 | 5 | 10 | 3 |
| 3 | INF | 5 | 0 | 5 | 2 |
| 4 | INF | 10 | 5 | 0 | 7 |
| 5 | INF | 3 | 2 | 7 | 0 |
private void solveC() {
final long CONST_INF = Long.MAX_VALUE / 10;
int n = nextInt();
int m = nextInt();
long[][] graph = new long[n][n];
/*
*initialisation du graphe
* [1]Avec matrice adjacente comprenant[1]Créer une matrice adjacente sans
*/
for (int i = 0; i < n; i++) {
Arrays.fill(graph[i], CONST_INF);
graph[i][i] = 0;
}
for (int i = 0; i < m; i++) {
/*
*Selon l'indice-1 et capturer
*/
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 - Méthode Floyd pour mettre à jour les sommets
*/
/*
*Si vous démarrez l'indice à partir de 1, il ne sera pas mis à jour pour 1
*/
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);
}
Recommended Posts