Ich denke, der Engpass bei der Teilnahme an wettbewerbsfähiger Programmierung in Java ist die Begrenzung der Ausführungszeit. In einigen Fällen dauert die Plattform, an der ich teilnehme, 20 bis 20 Mal länger als C ++ 14 und 4 Mal länger als Python 3 (Java 8 Open JDK 1.8.0).
Obwohl ich die Logik zur Lösung des Problems entwickelt habe, habe ich oft das Gefühl, dass ich es nicht beenden kann, da die Antwort aufgrund der begrenzten Ausführungszeit nicht korrekt ist.
Daher möchte ich den Inhalt der schwierigen Probleme, auf die ich kürzlich gestoßen bin, sowie die Maßnahmen und Richtlinien für solche Probleme mitteilen. Es ist eine Notiz eines Anfänger-Programmierers (nicht bescheiden), also zögern Sie nicht, einen Kommentar abzugeben.
- Bei den Eingaben von 2 oder mehr geraden A-Werten und 1 oder mehr natürlichen A-Zahlen die Mitte der Menge für eine ungerade Anzahl von Zahlen, wobei jeweils eine A-Ganzzahl in der Reihenfolge der Eingabe ausgeschlossen ist. Geben Sie die Werte der Reihe nach aus. * *
- Allerdings ・ Es ist garantiert, dass A immer 10 ^ 5 oder weniger ist. -Es wird garantiert, dass alle Eingaben Ganzzahlen sind. * *
- Verarbeitungsbeispiel: * input *6 (==A) 7 1 4 2 6 9 (Eingabe von 1 oder mehr angegebenen natürlichen Zahlen (als Testfall angegeben)) *
output
Klicken Sie hier für eine Beschreibung des Medians https://ja.wikipedia.org/wiki/%E4%B8%AD%E5%A4%AE%E5%80%A4
Aus dem Inhalt des Problems
** - Speichern Sie den eingegebenen Wert in einem numerischen Array (in Array oder ArrayList). ** ** ** ** - Löschen Sie die Elemente in der angegebenen Reihenfolge aus diesem Array. ** ** ** ** - Sortieren Sie das Array. ** ** ** ** ・ (A / 2) - Den ersten Wert ausgeben. ** ** **
Sie können den Ablauf der Verarbeitung sehen. Das bedeutet
-Löschen Sie die Elemente in der Reihenfolge von diesem Array. -Sortieren Sie das Array. ・ (A / 2) - Geben Sie den ersten Wert aus. Sie müssen nur den iterativen Prozess schreiben.
Hier ist der Code, den ich zuerst geschrieben habe.
Main.java
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
ArrayList<Integer> arr = new ArrayList<>();
for (int i = 0; i < n; i++) {
arr.add(s.nextInt());
}
ArrayList<Integer> arrCopy = (ArrayList<Integer>) arr.clone();
for(int j=0;j<n;j++){
/*★*/ arr.remove(j);
/*★*/ Collections.sort(arr);
System.out.println(arr.get((n / 2) - 1));
/*★*/ arr = (ArrayList<Integer>) arrCopy.clone();
}
}
}
Dieser Code überschreitet jedoch die Ausführungszeit in der Produktionsumgebung. Aus, weil die Liste an der Position ★ für A-mal gelöscht, sortiert und dupliziert wird. Die ArrayList-Klasse hat eine variable Anzahl von Elementen, hat jedoch die Eigenschaft, dass sie tendenziell langsamer als die Array-Klasse ausgeführt wird.
Übrigens bestand der Inhalt der Aufgabe darin, jeweils den Medianwert auszugeben. Sie müssen die Elemente einzeln löschen und den Medianwert angeben, aber Sie sollten ArrayList nicht verwenden. …
Tatsächlich gibt es für den Medianwert dieses Problems ** unabhängig von der Anzahl der Elemente zwei Kandidaten **.
Zum Beispiel
1，2，3，4，5，6
Selbst wenn Sie die Zahlen nacheinander von 1 bis 6 löschen, ist der Medianwert bei der gegebenen Zahl immer entweder ** 3 ** oder ** 4 **.
Wenn 1,2,3 gelöscht werden, ist 4 der Medianwert, Wenn 4,5,6 gelöscht wird, wird 3 als Medianwert bestimmt.
Hier ist der Code, den ich geschrieben habe, nachdem ich dies berücksichtigt habe.
Main.java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int[] sortedArr = new int[n];
for (int i = 0; i < n; i++) {
sortedArr[i] = s.nextInt();
}
int[]originArr=sortedArr.clone();
Arrays.sort(sortedArr);
int firstNum=sortedArr[(n/2)-1];
int secondNum=sortedArr[n/2];
for(int j=0;j<n;j++){
if(originArr[j]<secondNum){
System.out. println(secondNum);
}
else{
System.out.println(firstNum);
}
}
}
}
Dies ist bis zu dem Punkt gleich, an dem die eingegebenen Nummern im Array gespeichert werden (obwohl die Array-Klasse unterschiedlich ist). Danach speichert (n / 2) die 1. und n / 2. Zahl als int-Werte. Dann vergleicht es die gelöschte Zahl mit der kleinen Anzahl von Median-Kandidaten und gibt einen beliebigen Wert aus.
In diesem Code müssen Sie das Array in der Ausgabe für Anweisung nicht bearbeiten. Und selbst in Java können Sie die Zeitbeschränkung beibehalten, auch wenn die Elemente des Arrays variabel sind.
Zunächst einmal ist es falsch anzunehmen, dass sich der Medianwert in jedem gelöschten Array dynamisch ändert. Der Faktor, der eine solche Prämisse gemacht hat, ist die Ungeduld, dass "ich den Code schnell schreiben und einreichen muss".
Ich denke, die Wettbewerbsprogrammierung ist eine spezielle Umgebung für Programmierer, und für die meisten Teilnehmer muss ich Code schreiben, der in schwierigen Wettbewerbszeiten funktioniert. Mit anderen Worten, es ist leicht, ungeduldig zu werden, weil Sie schnell Code schreiben möchten.
Für diejenigen, die bis zu einem gewissen Grad daran gewöhnt sind (diejenigen, die andere Fragen beantworten können als diejenigen, die nur wenige Prozent der Gesamtzahl beantworten können), ist die erforderliche Zeit ein wichtigerer Faktor für die Bestimmung des Teilnehmerrankings als die Anzahl der richtigen Antworten auf die Frage. Insbesondere.
In einer eingeschränkten Umgebung und bei Teilnahme an wettbewerbsfähigen Programmen wie Java in einer "nachteiligen" Sprache ・ Schreiben Sie mehrere Prozesse in einen sich wiederholenden Satz. ・ Verwenden Sie bequeme Klassen
eher, als, ・ Untersuchen Sie die Regeln für Antworten ・ Auch wenn wiederholte Anweisungen verwendet werden, wird die Verarbeitung in ihnen minimiert.
Das ist eine wichtige Strategie, die mir auch ein Gebot ist, und ich wollte sie diesmal teilen.
Das ist alles. Wenn Sie Fehler oder andere Lösungen haben, teilen Sie uns dies bitte in den Kommentaren mit.
Recommended Posts