AtCoder Beginner Contest 167 von C-Problem (C-Skill Up) von Ich habe das Kommentarvideo nicht gesehen. Oder es ist ein Artikel für diejenigen, die besorgt sind, wenn sie es verstehen können.
Ich habe den Kommentar zum Video gesehen, aber ich habe ihn für die Organisation zusammengestellt.
Das Kommentarvideo ist also auch sehr leicht zu verstehen Bitte beachten Sie auch dies. Das C-Problem liegt zwischen 21:30 und 42:00 Uhr. Das Kommentarvideo ist hier.
** So probieren Sie alle Zahlenkombinationen von 1 bis N aus **.
Die Problemstellung kann wie folgt zusammengefasst werden.
Es gibt M Algorithmen, die Takahashi lernen möchte, Es gibt N Algorithmus-Nachschlagewerke im Buchladen.
Takahashi hat ein Budget, um alle Nachschlagewerke zu kaufen, Wenn möglich, möchte ich effizient lernen und die minimalen Kosten einhalten.
In welcher Reihenfolge sollten Sie die Nachschlagewerke kaufen und lesen, um das meiste Geld zu sparen? Finden Sie die Mindestkosten.
** N Nachschlagewerke kaufen Alle Kombinationen ausprobieren **
Es gibt "1 << N" -Kombinationen, um N Nachschlagewerke zu kaufen.
<< ist eine Schichtoperation. "1 << N" bedeutet, 1 um N Teile nach links zu verschieben.
Verschiebungsoperationen werden binär betrachtet.
Binärzahl
0: 0000
1: 0001
2: 0010
3: 0011
4: 0100
5: 0101
6: 0110
7: 0111
8: 1000
Beispiel: 1 << 3 Es bedeutet also, 0001 um drei nach links zu verschieben Es wird 0001000 sein. Daher ist es "8" in Dezimalzahl.
Wenn daher N von N Büchern "3" ist, ist die Kombination "8 Muster".
Schauen Sie sich die Binärzahlen 0-7 oben an. Wenn Sie auf die 3 Ziffern von rechts achten, können Sie sehen, dass alle Muster von 0 bis 7 abgedeckt sind.
Stellen Sie sich jede Ziffer vor, ob Sie jedes Nachschlagewerk kaufen möchten.
Beispiel: Wenn es 3 Nachschlagewerke gibt
000-> Fall, in dem Sie nicht einmal ein Buch kaufen
001-> Der Fall, in dem Sie das erste Nachschlagewerk kaufen, aber nicht das zweite und dritte
010-> Der Fall, in dem Sie das zweite Nachschlagewerk kaufen, aber nicht das erste und dritte
011-> Ein Fall, in dem Sie das erste und zweite Nachschlagewerk kaufen, aber nicht das dritte
100-> Der Fall, in dem Sie das dritte Nachschlagewerk kaufen, aber nicht das erste und das zweite
101-> Ein Fall, in dem Sie das erste und dritte Nachschlagewerk kaufen, aber nicht das zweite
110-> Ein Fall, in dem Sie das zweite und dritte Nachschlagewerk kaufen, aber nicht das erste
111-> Fall, um alle zu kaufen
class Main {
public static void main(String[] args) {
int patternCount = 1 << 3;
System.out.printf("patternCount=%d\n", patternCount);
for (int i = 0; i < patternCount; i++) {
System.out.println(Integer.toBinaryString(i));
}
}
}
↑ Es werden 8 Muster wiederholt, sodass Sie einfach 8 Mal eine Schleife ausführen können. Ich habe versucht, 0 bis 7 binär auszugeben.
Ausgabeergebnis
patternCount=8
0
1
10
11
100
101
110
111
Schauen wir uns Bücher an, die gekauft werden sollen, und Bücher, die nicht gekauft werden sollen, je nachdem, ob jede binäre Ziffer 1 ist.
Wenn es 001 ist, wird das erste Nachschlagewerk gekauft, das zweite und dritte jedoch nicht. Wenn es 110 ist, kaufen Sie das zweite und dritte Nachschlagewerk, aber nicht das erste
Es ist wie es ist.
Mit anderen Worten
Beim Kauf des ersten Buches ist die erste Zahl, die von rechts zählt, 1. Beim Kauf des zweiten Buches ist die zweite Zahl von rechts 1. Beim Kauf des dritten Buches ist die dritte Zahl von rechts 1.
Korrekt.
Verwenden Sie den Operator "&", um herauszufinden, ob die in binär angegebene Ziffer 1 ist.
Der Operator "&" wird nur dann auf 1 gesetzt, wenn beide Ziffern in der Binärdarstellung 1 sind.
Lassen Sie es uns zum leichteren Verständnis binär ausdrücken.
1111 & 0001 -> 0001 1111 & 1001 -> 1001 1000 & 1001 -> 1000
Auf diese Weise ist es eine Operation, die jede Ziffer der linken und rechten Binärzahl vergleicht und diese Ziffer nur dann auf 1 setzt, wenn beide 1 sind.
Nutzen Sie dies
Es wird sein.
class Main {
public static void main(String[] args) {
int n = 3;
System.out.printf("n=%d\n", n);
int patternCount = 1 << n;
System.out.printf("patternCount=%d\n", patternCount);
for (int i = 0; i < patternCount; i++) {
System.out.println(Integer.toBinaryString(i));
for (int j = 0; j < n; j++) {
if ( (i & 1<<j) == 1<<j) {
System.out.printf(" %Kaufen Sie das d-te Nachschlagewerk\n", j + 1);
}
}
}
}
}
↑ Prüfen Sie auf diese Weise, ob jede Ziffer der Binärzahl 1 ist. Das Ausgabeergebnis ist wie folgt.
n=3
patternCount=8
0
1
Kaufen Sie das erste Nachschlagewerk
10
Kaufen Sie ein zweites Nachschlagewerk
11
Kaufen Sie das erste Nachschlagewerk
Kaufen Sie ein zweites Nachschlagewerk
100
Kaufen Sie ein drittes Nachschlagewerk
101
Kaufen Sie das erste Nachschlagewerk
Kaufen Sie ein drittes Nachschlagewerk
110
Kaufen Sie ein zweites Nachschlagewerk
Kaufen Sie ein drittes Nachschlagewerk
111
Kaufen Sie das erste Nachschlagewerk
Kaufen Sie ein zweites Nachschlagewerk
Kaufen Sie ein drittes Nachschlagewerk
Jetzt haben wir die Grundlage, um dieses Problem zu lösen. Probieren Sie alle Muster aus, um die niedrigsten Anschaffungskosten zu ermitteln.
Im folgenden Quellcode ist C-Problem AC.
import java.util.*;
class Main {
final static int INF = 1001001001;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//Eingabedaten in Variablen speichern
int n = sc.nextInt();
int m = sc.nextInt();
int x = sc.nextInt();
int[][] a = new int[12][12];
int[] c = new int[n];
for (int i = 0; i < n; i++) {
c[i] = sc.nextInt();
for (int j = 0; j < m; j++) {
a[i][j] = sc.nextInt();
}
}
sc.close();
//Antworten=Da es sich um den Mindestwert der Kosten handelt, initialisieren Sie ihn zum Vergleich des Mindestwerts mit einer großen Zahl.
int ans = INF;
//Überprüfen Sie alle Kombinationsmuster
for (int s = 0; s < 1<<n; s++) {
int cost = 0; //Die Kosten für diese Kombination
int[] d = new int[m]; //Verständnis jedes Algorithmus in dieser etw-Kombination
//Überprüfen Sie, ob jedes Bit binär 1 ist
for (int i = 0; i < n; i++) {
//Wenn das i-te Bit von rechts 1 ist, fügen Sie die Kosten und den Algorithmus als Referenz für den Kauf hinzu.
if ( (s & 1<<i) == 1<<i) {
//Kosten hinzufügen
cost += c[i];
//Fügen Sie zum Verständnis jedes Algorithmus hinzu
for (int j = 0; j < m; j++) {
d[j] += a[i][j];
}
}
}
//Überprüfen Sie, ob das Verständnis aller Algorithmen x überschreitet
boolean ok = true;
for (int j = 0; j < m; j++) {
if (d[j] < x) ok = false; //Wenn auch nur einer kleiner als x ist.
}
//Wenn die Prüfung in Ordnung ist, werden die Kosten den Mindestwert aktualisieren.
if (ok) ans = Math.min(ans, cost);
}
//Ans bleibt INF, wenn es kein Muster gibt, in dem das Verständnis aller Algorithmen x überschreitet
if (ans == INF) System.out.println(-1);
else System.out.println(ans);
}
}
Was haben Sie gedacht?
** Probieren Sie alle Zahlenkombinationen von 1 bis N aus **
Recommended Posts