Heim >Java >javaLernprogramm >Wie man Greedy und Enumeration in Java verwendet
Wie man Greedy und Enumeration in Java verwendet
- 王林nach vorne
- 2023-05-20 11:46:461093Durchsuche
#试#: Lernen Sie, den Wissenspunkt anhand des Datenbereichs zu erraten ## 🎜🎜#Im Allgemeinen 1S-Zeitlimit, die Zeitkomplexität kann bis zu etwa 1E8 betragen (Python und Java sind geringer, daher wird die Verwendung von C C /c++ empfohlen schriftliche Testfragen stellen).
# 🎜🎜#O(n*2 ^n) |
Drucksuche 🎜# n Bereich 200 oder weniger: |
O(n ^3) |
| # 🎜🎜# | n Bereich innerhalb 3000: | O (n^2)
|
O(n√n) |
gewalttätige Suchfaktoren usw. #🎜 🎜##🎜 🎜# |
n Bereich 1e6 oder weniger: |
| #🎜🎜 ##🎜 🎜# Die binäre Antwort verwendet verschiedene STL- und Set-Euler-Siebe usw. Innerhalb von 1e7: |
O(n) | # ?? 🎜#n Bereich innerhalb von 1e14: # 🎜🎜 ## 🎜🎜#o (√n)#🎜🎜 ## 🎜🎜 ## 🎜🎜 ## 🎜🎜#Finden Sie Divisors und Divisors#🎜🎜 ## 🎜🎜 ## 🎜🎜 ## 🎜🎜 ## 🎜 🎜#Gierig:Gierig bedeutet, bei jedem Schritt die aktuell optimale Wahl zu treffen. Die im Allgemeinen gelösten Probleme weisen die folgenden Merkmale auf: Lokale Optimalität kann zu globaler Optimalität führen. Bitte beachten Sie, dass Gier kein Allheilmittel ist! Es gibt n Artikel. Jedes Element hat einen Wert v[i] und ein Gewicht w[i]. Nehmen Sie nun Gegenstände mit, deren Gesamtgewicht m nicht überschreitet. Wie hoch ist der maximale Wert der mitgenommenen Gegenstände? (Rucksackproblem)
Aufzählung:1. Naive AufzählungWie der Name schon sagt, verwenden Sie eine for-Schleife, um alle Situationen aufzuzählen. 2. ZustandsdruckaufzählungVerwenden Sie die Eigenschaften von n-base zur Aufzählung. Geeignet für Szenarien: Es gibt insgesamt n Elemente, jedes Element hat m Zustände, alle Zustände aller Elemente werden aufgelistet, die Komplexität beträgt O(m^n). So schreiben Sie eine binäre Zustandsaufzählung: Klassisches Problem: Gegeben n Zahlen a1, a2 ... an, jede Zahl ist optional, listen Sie alle möglichen Lösungen auf. for(int i=0;i<1<<n;i++){ //i为1到2^n的状态压缩值 2^n
int p=i; //先将i取出
int sum=0; //用一个变量维护取出的数之和
for(j=0;j<n;j++){ //转为二进制进行操作
sum+=p%2*a[j]; //这句话是求取出来的数之和。p%2为对应二进制位
//这里也可以进行其他操作，不一一举例。
p/=2; //求下一个二进制位
}
//这里可以添加想要的操作。
}Algorithmusfrage 1:chika und Satsuma (mit PriorityQueue+Comparator) Schwierigkeit ⭐⭐ chika isst sehr gerne Satsumas. Jede Mandarine hat einen gewissen Grad an Säure und Süße. Chika isst gerne süße, aber keine sauren. Chika hat k Mandarinen gegessen. Sie wird die Summe aus Süße und Säure der Mandarinen berechnen, die sie gegessen hat. Chika möchte die größtmögliche Süßesumme erreichen. Bei mehreren Optionen möchte sie, dass der Gesamtsäuregehalt so gering wie möglich ist. Sie möchte wissen, wie hoch die endgültige Gesamtsäure und Gesamtsüße ist? Informationen zur Frage: Sortieren Sie zuerst nach Süße in absteigender Reihenfolge und dann nach Säure in aufsteigender Reihenfolge (behalten Sie die vorherige absteigende Reihenfolge von Süße zuerst und aufsteigender Säure zweitens bei) Eingabebeschreibung: Die erste Zeile enthält zwei positive ganze Zahlen n und k stellt die Gesamtzahl der Mandarinen bzw. die Zahl der von Chika gegessenen Mandarinen dar. (1≤k≤n≤200000) Die zweite Zeile enthält n positive ganze Zahlen ai, die den Säuregehalt jeder Mandarine darstellen. (1≤ai≤1e9) Die zweite Zeile enthält n positive ganze Zahlen bi, die die Süße jeder Mandarine darstellen. (1≤bi≤1e9) Ausgabebeschreibung: Zwei positive ganze Zahlen, durch Leerzeichen getrennt. Stellt den Gesamtsäuregehalt bzw. die Gesamtsüße dar. BeispielEingabe
Ausgabe
Anweisungen Wählen Sie Nr. 1 und Nr. 3 Mandarinen, der Gesamtsäuregehalt beträgt 5, insgesamt Der Süßegrad beträgt 7, was die optimale Lösung darstellt. import java.io.*;
import java.util.*;
public class Main{
public static class Orange{
int acid;
int sweet;
public Orange(int acid, int sweet){
this.acid = acid;
this.sweet = sweet;
}
public Orange(){}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] tmp = br.readLine().split(" ");
int n = Integer.parseInt(tmp[0]);
int k = Integer.parseInt((tmp[1]));
String[] ai = br.readLine().split(" ");
String[] bi = br.readLine().split(" ");
//定义一个优先队列，并根据指定的比较器对其元素进行排序。
PriorityQueue<Orange> queue = new PriorityQueue<>((Orange o1, Orange o2)->{
//匿名内部类以lambda的形式定义排序规则
if(o1.sweet == o2.sweet){
return o1.acid - o2.acid;
}else{
return o2.sweet - o1.sweet;
}
});
for(int i = 0; i < n; i++){
Orange orange = new Orange();
orange.acid = Integer.parseInt(ai[i]);
orange.sweet = Integer.parseInt(bi[i]);
queue.add(orange);
}
long totalAcid = 0;
long totalSweet = 0;
for(int i = 0; i < k; i++){
Orange o = queue.poll();
totalAcid += o.acid;
totalSweet += o.sweet;
}
System.out.println(totalAcid + " " + totalSweet);
}
}Zweck: Verstehen Sie, was Gier ist, und Sie können die Verwendung von PriorityQueue+Comparator in Betracht ziehen, wenn Sie mit Priorität entwerfen. Algorithmusfrage 2:Du und das Segelboot Schwierigkeit ⭐⭐ Dein Vater ist Kapitän. Sie lieben das Meer schon seit Ihrer Kindheit. An diesem Tag machte sie sich mit einem Segelboot auf den Weg. Es gibt viele Schätze auf dem Meer und die Koordinaten jedes Schatzes sind bekannt. Ihre Anfangskoordinaten sind (0,0). Sie möchte zwei Schätze erkunden und dann zum Ausgangspunkt zurückkehren. Sie möchten, dass die Strecke so kurz wie möglich ist. Sie wollte wissen, wie lang die kürzeste Route sei? Informationen zur Frage: Zählen Sie die beiden for-Schleifen auf und speichern Sie den kürzesten Pfad. Eingabebeschreibung: Die erste Zeile ist eine positive ganze Zahl n, die die Anzahl der Schätze darstellt. (2≤n≤2000) In den nächsten n Zeilen enthält jede Zeile 2 positive ganze Zahlen xi, yi, die die Koordinaten des i-ten Schatzes darstellen (-3000≤xi,yi≤3000) Dafür gibt es keine Garantie Es wird nicht zwei geben. Der Schatzort ist derselbe. Das heißt, Sie können beide Schätze am selben Ort erkunden. Ausgabebeschreibung: Die Länge der kürzesten Route. Behalten Sie 6 Nachkommastellen bei. BeispielEingabe
Ausgabe
Erläuterung
import java.io.*;
import java.util.*;
class Point{
double x;
double y;
}
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Point[] points = new Point[n];
for(int i=0;i<n;i++){
String[] strings = br.readLine().split(" ");
Point point = new Point();
point.x = Integer.parseInt(strings[0]);
point.y = Integer.parseInt(strings[1]);
points[i] = point;
}
double min = Double.MAX_VALUE;//定义最大值，寻找较小值
//双层遍历枚举
for (int i=0;i<n-1;i++) {
for (int j=i+1;j<n;j++) {
double temp = Math.sqrt(points[i].x*points[i].x + points[i].y*points[i].y)
+ Math.sqrt(points[j].x*points[j].x + points[j].y*points[j].y)
+ Math.sqrt((points[i].x-points[j].x)*(points[i].x-points[j].x) + (points[i].y-points[j].y)*(points[i].y-points[j].y));
min = Math.min(min, temp);
}
}
System.out.println(String.format("%.6f", min));
}
}Zweck: Verstehen, was eine Aufzählung ist, obwohl es eine ist von einem aufgeführt, aber es gibt immer noch Möglichkeiten zur Optimierung basierend auf der Realität. Zum Beispiel zählt die zweistufige Schleife in dieser Frage nur die Hälfte der Situation auf: Denn gesucht wird die Entfernung, die nichts mit den beiden Endpunkten zu tun hat. Denken: Was sollen wir tun, wenn mehr als zwei Schatztruhen beschafft werden müssen? ? ? Sie können sich auf die nächste Frage beziehen. Algorithmusfrage 3:Digitale Färbung Schwierigkeit ⭐⭐⭐ Xiaohong hat eine positive ganze Zahl X erhalten. Sie könnte einige der Ziffern rot färben. Dann möchte sie, dass die Summe aller rot gefärbten Ziffern gleich der Summe der ungefärbten Ziffern ist. Sie weiß nicht, ob sie ihr Ziel erreichen kann. Kannst du es ihr sagen? Eingabebeschreibung: Eine positive Ganzzahl X, 1 Beispiel 1 Eingabe 1234567AusgabeJa AnweisungenFärben Sie einfach 3, 4 und 7 rot, also 3+4+7=1+2+5+ 6 Beispiel 2 Eingabe 23AusgabeNein Erklärung |
Das obige ist der detaillierte Inhalt vonWie man Greedy und Enumeration in Java verwendet. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!