Wie man Greedy und Enumeration in Java verwendet

#试#: 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).

n Bereich innerhalb von 20: Dreidimensionale dpzweidimensionaler Bereich 1e5 Innerhalb: #🎜🎜 #O(nlogn) # ?? 🎜#

# 🎜🎜#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) Strategie 1: Ordnen Sie die Werte in absteigender Reihenfolge an und nehmen Sie dabei jeweils den höchsten Wert. Strategie 2: Ordne die Gewichte in aufsteigender Reihenfolge an und nimm jedes Mal das leichteste Gewicht. Strategie 3: Ordnen Sie in absteigender Reihenfolge nach Wert/Gewicht (d. h. Einheitswert) und nehmen Sie jedes Mal diejenige mit dem höchsten Einheitswert. Aufzählung: 1. Naive Aufzählung Wie der Name schon sagt, verwenden Sie eine for-Schleife, um alle Situationen aufzuzählen. 2. Zustandsdruckaufzählung Verwenden 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. Beispiel Eingabe 3 2 1 3 4 2 2 5 Ausgabe 5 7 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. Beispiel Eingabe 2 1 0 0. 1 Ausgabe 3.414214 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 1234567 Ausgabe Ja Anweisungen Färben Sie einfach 3, 4 und 7 rot, also 3+4+7=1+2+5+ 6 Beispiel 2 Eingabe 23 Ausgabe Nein Erklärung 显然无论如何都不能完成染色。 import java.util.*; import java.io.*; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Long x= Long.parseLong(br.readLine()); //循环0到2^18来展现所有的可能性 for(int i=0;i<1<<19;i++){ long p=i,s1=0,s2=0,temp=x; //将p拟化为2进制，通过j来寻尾。寻一次p就对应的二进制数就少一位。 for(int j=0;j<19;j++){ if(p%2==1)s1+=temp%10; else s2+=temp%10; p/=2; temp/=10; } if(s1==s2){ System.out.println("Yes"); System.exit(0); } } System.out.println("No"); } } 这题使用的是状压枚举 只有两种状态就拟成2进制，假如有3种状态就拟成3进制（上面的代码会有些许改变，n种状态也一样） for(int i=0;i<1<<19;i++) //修改成 for(int i=0;i<19;i++) p1[i]=p1[i-1]*3; for(int i=0;i<p1[i];i++){} 当然这题也可以使用背包或dfs来解答。 算法题4：  ranko的手表   难度 ⭐⭐⭐⭐ ranko 的手表坏了，正常应该显示 xx:xx 的形式（4 个数字），比如下午 1 点半应该显示 13:30 ，但现在经常会有一些数字有概率无法显示。 Ranko checked the time at t1 and then again at t2 after some time had passed.。她想弄清楚t1和t2两个时间点之间的最大和最小时间间隔是多少 保证t1在t2之前（且t1和t2不等）。 t1和t2在同一天的 00:00 到 23:59 之间。  输入描述: 两行输入两个时间，为 xx:xx 的形式。x可以是数字或字符'?'，当为'?'时表示该数字未显示。保证输入是合法的。 输出描述: 一行输出两个整数，分别代表 t1 和 t2 相距时间的最小值和最大值（单位分钟）。 示例1 输入 18:0? 2?:1? 输出 121 319 说明 相距最小的时间为 18:09 到 20:10 ，相距121分钟。 相距最大的时间为 18:00 到 23:19 ，相距319分钟。 import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s1 = br.readLine(); String s2 = br.readLine(); ArrayList<Integer> a1 = new ArrayList<>(); ArrayList<Integer> a2 = new ArrayList<>(); for(int i = 0; i < 60*24; i++){ int hour = i/60, minute = i%60; if((hour/10 == s1.charAt(0)-&#39;0&#39; || s1.charAt(0) == &#39;?&#39;) && (hour%10 == s1.charAt(1)-&#39;0&#39; || s1.charAt(1) == &#39;?&#39;) && (minute/10 == s1.charAt(3)-&#39;0&#39; || s1.charAt(3) == &#39;?&#39;) && (minute%10 == s1.charAt(4)-&#39;0&#39; || s1.charAt(4) == &#39;?&#39;)) a1.add(i); if((hour/10 == s2.charAt(0)-&#39;0&#39; || s2.charAt(0) == &#39;?&#39;) && (hour%10 == s2.charAt(1)-&#39;0&#39; || s2.charAt(1) == &#39;?&#39;) && (minute/10 == s2.charAt(3)-&#39;0&#39; || s2.charAt(3) == &#39;?&#39;) && (minute%10 == s2.charAt(4)-&#39;0&#39; || s2.charAt(4) == &#39;?&#39;))a2.add(i); } int min= Integer.MAX_VALUE, max = Integer.MIN_VALUE; for(int i = 0; i<a1.size();i++){ for(int j = 0; j<a2.size();j++){ if(a1.get(i)<a2.get(j)){ min = Math.min(min,a2.get(j)-a1.get(i)); max = Math.max(max,a2.get(j)-a1.get(i)); } } } System.out.print(min + " " + max); } }

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!