Java에서 탐욕과 열거를 사용하는 방법
- 王林앞으로
- 2023-05-20 11:46:461032검색
작성 테스트 기술: 데이터 범위를 기반으로 지식 포인트를 추측하는 방법을 배웁니다.
일반적으로 1초의 시간 제한이 있는 질문의 경우 시간 복잡도는 약 1e8에 도달할 수 있습니다(Python 및 Java는 덜하므로 C를 사용하는 것이 좋습니다). 필기 시험 문제의 경우 /c++).
n 범위 20 이하: |
O(n*2^n) |
압력 검색 |
| n 범위 200 이내: | O (n^3) | 3차원 dp |
| n 범위 3000 이하: | O(n^2) | 2차원 dp 백팩 열거 2차원 접두어 합 등 | 1e6 이내의 범위:
O(nlogn) |
두 점 답은 다양한 stl을 사용하여 오일러 체 등을 찾는 것입니다. |
n 사용 > 이내 는 1e14의 범위: |
O(√n) |
제수와 제수의 개수를 구하세요 |
욕심:욕망은 모든 단계에서 현재 최적의 선택을 한다는 의미입니다. 일반적으로 해결되는 문제는 다음과 같은 특징을 가지고 있습니다: 지역적 최적성은 전역적 최적성으로 이어질 수 있습니다. 욕심은 만병통치약이 아니라는 점 주의해주세요! n개 항목이 있습니다. 각 항목은 값 v[i]와 가중치 w[i]를 갖습니다. 이제 총 무게가 m를 초과하지 않는 품목을 가져가세요. 가져가는 품목의 최대 가치는 얼마인가요? (배낭 문제)
열거:1. 순진한 열거이름에서 알 수 있듯이 for 루프를 사용하여 모든 상황을 열거합니다. 2. 상태 압력 열거n-base의 속성을 사용하여 열거합니다. 시나리오에 적합: 총 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:chika와 사츠마 (PriorityQueue+Comparator 사용) 난이도 ⭐⭐ chika는 사츠마를 아주 좋아합니다. 귤 하나하나에는 어느 정도의 신맛과 단맛이 있습니다. 치카는 달콤한 것을 좋아하지만 신 것은 좋아하지 않습니다. 치카는 k개의 귤을 먹었습니다. 총 n개의 귤이 있습니다. 그녀는 자신이 먹은 귤의 단맛과 신맛의 합을 계산합니다. 치카는 최대한의 단맛을 얻고 싶어합니다. 옵션이 여러 개인 경우 총 산도가 최대한 낮아지기를 원합니다. 그녀가 알고 싶은 것은 최종 총산도와 총 단맛이 얼마일까요? 질문 정보: 단맛을 내림차순으로 먼저 정렬한 다음 산도를 오름차순으로 정렬합니다(이전의 단맛 내림차순을 먼저 유지하고 산도를 두 번째로 오름차순으로 유지) 입력 설명: 첫 번째 줄에는 두 개의 양의 정수 n이 있습니다. k는 각각 총 감귤의 수와 치카가 먹는 감귤의 수를 나타낸다. (1≤k≤n≤200000) 두 번째 줄에는 각 귤의 산도를 나타내는 n개의 양의 정수 ai가 있습니다. (1≤ai≤1e9) 두 번째 줄에는 각 만다린 오렌지의 단맛을 나타내는 n개의 양의 정수 bi가 있습니다. (1≤bi≤1e9) 출력 설명: 공백으로 구분된 두 개의 양의 정수입니다. 전체 산도와 전체 단맛을 각각 나타냅니다. ExampleInput
Output
Instructions 1번을 선택하고 No .감귤 3개, 총 산도는 입니다. 5 , total 단맛 수준은 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)입니다. 그녀는 두 개의 보물을 탐험하고 출발점으로 돌아가고 싶어합니다. 경로를 최대한 짧게 하고 싶습니다. 그녀는 최단 경로의 길이가 얼마나 되는지 알고 싶었습니다. 질문 정보: 두 개의 for 루프를 열거하고 최단 경로를 저장하세요. 입력 설명: 첫 번째 줄은 보물의 개수를 나타내는 양의 정수 n입니다. (2≤n≤2000) 다음 n 줄에는 각 줄에 i번째 보물의 좌표를 나타내는 2개의 양의 정수 xi, yi가 포함됩니다(-3000≤xi,yi≤3000) 두 개는 없을 것입니다. 보물 위치는 동일합니다. 즉, 같은 위치에서 두 보물을 모두 탐색할 수 있다는 뜻입니다. 출력 설명: 최단 경로의 길이입니다. 소수점 이하 6자리를 유지합니다. 예Input
Output
설명
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));
}
}목적: 열거형이지만 열거형이 무엇인지 이해합니다. 하나씩 나열되어 있지만 현실에 따라 최적화할 수 있는 방법은 여전히 있습니다. 예를 들어, 이 질문의 2단계 루프는 상황의 절반만 열거합니다. 왜냐하면 추구하는 것은 두 끝점과 아무 관련이 없는 거리이기 때문입니다. 생각하기: 얻어야 할 보물상자가 두 개 이상 있으면 어떻게 해야 할까요? ? ? 다음 질문을 참고하시면 됩니다. 알고리즘 질문 3:디지털 색칠 난이도 ⭐⭐⭐ Xiaohong은 양의 정수 X를 얻었습니다. 그녀는 숫자 중 일부를 빨간색으로 염색할 수 있었습니다. 그런 다음 그녀는 빨간색으로 칠해진 모든 숫자의 합이 염색되지 않은 숫자의 합과 같기를 원했습니다. 그녀는 자신의 목표를 달성할 수 있을지 모릅니다. 그녀에게 말해줄 수 있나요? 입력 설명: 양의 정수 X, 1 예제 1 Input 1234567OutputYes Instructions 3, 4, 7을 빨간색으로 염색하면 3+4+7=1+2+5+6 예제 2 Input 23OutputNo 설명 |
위 내용은 Java에서 탐욕과 열거를 사용하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!