Javaで貪欲と列挙を使用する方法
- 王林転載
- 2023-05-20 11:46:461079ブラウズ
筆記試験のスキル: データ範囲に基づいて知識ポイントを推測する方法を学ぶ# ペンでの質問）。
#O(n*2^n) | #圧力探索 /dfs 爆発探索 | n 範囲 200 以下: |
| O(n ^ 3) | ##3 次元 dpn 範囲 3000 以内: |
|
| 二次元 dp バックパック列挙二次元プレフィックスなど | # #n 範囲 1e5 以下: | |
##因子などの暴力的な検索 |
#n 範囲 1e6 以内: | O(nlogn) |
バイナリの答えはさまざまな stl を使用しますオイラーふるいなどを見つけます |
##n 範囲 1e7 以内: | O(n) |
| デュアルポイントニードル線形 DP 差動/プレフィックスおよび 1e14 内の | # N 範囲: |
((√N ) | #約数と約数の数を求める
貪欲:貪欲とは、あらゆる段階で最善の選択をすることを意味します。一般に解決される問題には、次のような特徴があります。局所的な最適性が全体的な最適性につながる可能性があります。 貪欲は万能薬ではないことに注意してください。 アイテムは n 個あります。各項目には値 v[i] と重み w[i] があります。 次に、総重量が m を超えないアイテムを取り出します。取り出したアイテムの最大値はいくらですか? (ナップザック問題)
列挙:1. 単純な列挙名前が示すように、for ループを使用してすべての状況を列挙します。 2. ステータスの列挙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; //求下一个二进制位
}
//这里可以添加想要的操作。
}アルゴリズムの質問 1:チカとサツマ (PriorityQueue Comparator の使用) 難易度 ⭐⭐ チカはサツマを食べるのがとても好きです。みかんにはそれぞれある程度の酸味と甘みがあり、千歌は甘いものは好んで食べますが、酸っぱいものは苦手です。 千花は k 個のみかんを食べました。合計 n 個のみかんがあります。彼女は食べたみかんの甘みと酸味の合計を計算します。チカは可能な限り最大の甘さの合計を取得したいと考えています。複数の選択肢がある場合、彼女は総酸性度をできるだけ小さくしたいと考えています。 彼女が知りたいのは、最終的な総酸味と総甘味は何でしょうか? 質問情報: 最初に甘味の降順、次に酸味の昇順で並べ替えます (前回の甘味の降順を維持し、次に酸味の昇順) 説明を入力してください: 最初の行には 2 つの正の整数 n と k があり、それぞれみかんの総数とチカが食べたみかんの数を表します。 (1≤k≤n≤200000) 2行目は、各みかんの酸味を表すn個の正の整数aiが入っています。 (1≤ai≤1e9) 2行目はn個の正の整数biで、みかんの甘さを表しています。 (1≤bi≤1e9) 出力の説明: スペースで区切られた 2 つの正の整数。それぞれ総酸味と総甘味を表します。 例入力
出力
説明 1番と3番のみかんを選択し、酸度の合計は5、合計は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 の使用を検討できます。 アルゴリズムの質問 2:あなたとヨット 難易度 ⭐⭐ あなたのお父さんは船長です。小さい頃から海が大好きだったんですね。その日、彼女は帆船に乗って出発した。 海にはたくさんの宝物があり、それぞれの宝物の座標はわかっています。初期座標は (0,0) です。彼女は 2 つの宝物を探索してから、原点に戻りたいと考えています。 ルートをできるだけ短くしたいと考えています。彼女が知りたかったのは、最短ルートの長さはどれくらいかということです。 質問情報: 2 つの for ループで列挙し、最短パスを保存します。 入力説明: 最初の行は、宝の数を表す正の整数 n です。 (2≤n≤2000) 次の n 行には、各行に 2 つの正の整数 xi と yi が含まれており、i 番目の宝物の座標を表します (-3000≤xi,yi≤3000) 同じ場所に 2 つの宝物が存在しないという保証はありません。つまり、同じ場所で両方の宝物を探索できるということです。 出力の説明: 最短パスの長さ。小数点以下は 6 桁にしてください。 例入力
出力
説明
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));
}
}目的: 列挙とは何かを理解します。 1 つずつリストされていますが、現実に基づいて最適化する方法はまだあります。 たとえば、この質問の 2 層ループは状況の半分だけを列挙しています。これは、求められるのは距離であり、2 つのエンドポイントとは何の関係もないためです。 思考: 取得する必要のある宝箱が 2 つ以上ある場合はどうすればよいでしょうか。 ? ?次の質問を参照してください。 アルゴリズムの問題 3: デジタルぬりえ 難易度 ⭐⭐⭐Xiaohong は正の整数 X を取得しました。彼女は数字のいくつかを赤く染めることができました。次に、赤く塗られたすべての数字の合計が、染まっていない数字の合計と等しくなるようにしたいと考えました。 彼女は目標を達成できるかどうかわかりませんでした。彼女に言ってもらえますか？ 入力の説明:正の整数 X, 1出力の説明:出力「Yes」 Xiaohongが必要に応じて染色を完了できることが前提です。それ以外の場合は「No」が出力されます。 #例 1 入力1234567出力はい 3、4、7を赤に染めるだけなので、3 4 7=1 2 5 6例2入力 23
No
|
##以上がJavaで貪欲と列挙を使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。