溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
今天小編給大家分享一下Java的貪心和枚舉怎么使用的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。
筆試技巧：學會根據數據范圍猜知識點
一般1s 時間限制的題目，時間復雜度能跑到 1e8 左右（ python 和 java 會少一些，所以建議大家使用c/c++ 做筆試題）。
n 范圍 20 以內： | O(n*2^n) | 狀壓搜索 /dfs 暴搜 |
n 范圍 200 以內： | O(n^3) | 三維 dp |
n 范圍 3000 以內： | O(n^2) | 二維 dp 背包 枚舉 二維前綴和等 |
n 范圍 1e5 以內： | O(n√n) | 暴力求因子等 |
n 范圍 1e6 以內： | O(nlogn) | 二分答案 使用各種 stl 并查集 歐拉篩等 |
n 范圍 1e7 以內： | O(n) | 雙指針 線性 dp 差 分 / 前綴和 |
n 范圍 1e14 以內： | O(√n) | 求約數和 約數個數 |
貪心指每一步都做出當前最優的選擇。一般解決的問題有如下特點：局部最優能導致全局最優。
請注意，貪心并不是萬能的！
有n個物品。每個物品有價值v[i]，以及重量w[i]。
現在取總重量不超過m的物品，問取的物品價值最大是多少？（背包問題）
策略1：按照價值降序排列，每次取價值最高的。
策略2 ：按照重量升序排列，每次取重量最輕的。
策略3 ：按照價值/重量（即單位價值）降序排列，每次取單位價值最高的。
顧名思義，用for循環枚舉所有情況。
借助n進制的性質進行枚舉。
適合場景：共有n個物品，每個物品有m種狀態，枚舉所有物品的所有狀態，復雜度為O(m^n)。
二進制狀壓枚舉的寫法：
典型場景： 總共有n個數：a1、a2……an，每個數可以取也可以不取，枚舉所有方案。
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; //求下一個二進制位
}
//這里可以添加想要的操作。
}chika和蜜柑（PriorityQueue+Comparator的使用）
難度 ??
chika很喜歡吃蜜柑。每個蜜柑有一定的酸度和甜度，chika喜歡吃甜的，但不喜歡吃酸的。
一共有n個蜜柑，chika吃k個蜜柑，將獲得所吃的甜度之和與酸度之和。chika想獲得盡可能大的甜度總和。如果有多種方案，她希望總酸度盡可能小。
她想知道，最終的總酸度和總甜度是多少？
題目信息：先按甜度降序排序，后按酸度升序排序（保持之前的甜度降序排序優先，酸度升序排序次之）
輸入描述:
第一行有兩個正整數n和k，分別代表蜜柑總數和chika吃的蜜柑數量。(1≤k≤n≤200000)
第二行有n個正整數ai，分別代表每個蜜柑的酸度。（1≤ai≤1e9）
第二行有n個正整數bi，分別代表每個蜜柑的甜度。（1≤bi≤1e9）
輸出描述:
兩個正整數，用空格隔開。分別表示總酸度和總甜度。
輸入
3 2
1 3 4
2 2 5
輸出
5 7
說明
選擇1號和3號蜜柑，總酸度為5，總甜度為7，為最優解。
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);
}
}目的：
了解什么是貪心，當設計到優先級時可以考慮使用PriorityQueue+Comparator。
you和帆船
難度 ??
you的父親是一名船長。因此you從小就很喜歡大海。這天，她乘著一艘帆船出發了。
大海上有很多寶藏，每個寶藏的坐標是已知的。you的初始坐標是（0,0）。她想探索兩個寶藏，然后回到初始點。
you希望航線盡可能短。她想知道，最短航線的長度是多少？
題目信息：兩個for循環枚舉一下，再保存最短路徑即可。
輸入描述:
第一行一個正整數n，代表寶藏的數量。（2≤n≤2000）
接下來的n行，每行2個正整數xi，yi，代表第i個寶藏的坐標（-3000≤xi,yi≤3000）
不保證不存在兩個寶藏位置相同。意思是，you可以在同一個位置探索這兩個寶藏。
輸出描述:
最短路線的長度。小數點后保留6位。
輸入
2
1 0
0 1
輸出
3.414214
說明
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));
}
}目的：
了解什么是枚舉，雖然是一個一個列舉，但是結合實際還是有優化的方式。
比如此題兩層循環只枚舉了一半的情況：因為所求的是距離，跟兩個端點無關。
思考：
假如不止有兩個寶箱需要被獲取，那么應該怎么辦？？？下一題可以參考一下。
數位染色
難度 ???
小紅拿到了一個正整數 X 。她可以將其中一些數位染成紅色。然后她想讓所有染紅的數位數字之和等于沒染色的數位數字之和。
她不知道能不能達成目標。你能告訴她嗎？
輸入描述:
一個正整數X ，1<= X <=10^18
輸出描述:
如果小紅能按要求完成染色，輸出"Yes"。否則輸出"No"。
輸入
1234567
輸出
Yes
說明
將3、4、7染成紅色即可，這樣3+4+7=1+2+5+6
輸入
23
輸出
No
說明
顯然無論如何都不能完成染色。
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來解答。
ranko的手表
難度 ????
ranko 的手表壞了，正常應該顯示 xx:xx 的形式（4 個數字），比如下午 1 點半應該顯示 13:30 ，但現在經常會有一些數字有概率無法顯示。
ranko 在 t1 時刻看了下時間，過了一段時間在 t2 時刻看了下時間。她想知道， t1 和t2這兩個時刻之間相距的時間的最大值和最小值是多少？
保證t1在t2之前（且t1和t2不等）。 t1和t2在同一天的 00:00 到 23:59 之間。
輸入描述:
兩行輸入兩個時間，為 xx:xx 的形式。其中 x 為數字或者字符 '?' ，問號代表這個數字沒有顯示。保證輸入是合法的。
輸出描述:
一行輸出兩個整數，分別代表 t1 和 t2 相距時間的最小值和最大值（單位分鐘）。
輸入
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)-'0' || s1.charAt(0) == '?') &&
(hour%10 == s1.charAt(1)-'0' || s1.charAt(1) == '?') &&
(minute/10 == s1.charAt(3)-'0' || s1.charAt(3) == '?') &&
(minute%10 == s1.charAt(4)-'0' || s1.charAt(4) == '?')) a1.add(i);
if((hour/10 == s2.charAt(0)-'0' || s2.charAt(0) == '?') &&
(hour%10 == s2.charAt(1)-'0' || s2.charAt(1) == '?') &&
(minute/10 == s2.charAt(3)-'0' || s2.charAt(3) == '?') &&
(minute%10 == s2.charAt(4)-'0' || s2.charAt(4) == '?'))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);
}
}以上就是“Java的貪心和枚舉怎么使用”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
