Article Catalog
This article mainly introduces greedy algorithms. The greedy algorithm is not a specific algorithm, but a strategy, one trick to control the enemy. The best choice every time is greedy algorithm. Therefore, greedy algorithms are often high efficiency and short code. Common greedy issues: interval issues, huffman trees, etc.
Example:HDU 2037 This summer will not be AC
Title is to give N programs. N programs have different start and end time, and require the most time to choose programs without time conflict.
This question is a classic greed. In essence, it is to find the maximum non -intersection range. For this question, the endpoint of the interval can intersect.
Method: Sort all programs from small to large. Then enumerate whether each range intersects with the previous interval. If not, the number of programs will be added.
C ++ code:
#include <iostream>
#include <algorithm>
using namespace std;
struct node{
int l, r;
}arr[100005];
int cmp(node a, node b){
return a.r < b.r;
}
int main(){
int n;
while(cin>>n, n){
int l, r;
for(int i = 0; i < n; i++){
cin>>l>>r;
arr[i].l = l;
arr[i].r = r;
}
sort(arr, arr + n, cmp);
int f = -2e9;
int res = 0;
for(int i = 0; i < n; i++){
if(arr[i].l >= f){
res ++;
f = arr[i].r;
}
}
cout<<res<<endl;
}
return 0;
}
ExamplePOJ 2376 Cleaning Shifts
Title: John has N -headed cows, each cow has different working hours. John divides the day into a time period, from 1 ~ T. He wants to have a cow to do a quiet work in each time period, and ask at least a few cows.
, also said, finding the least cows, the working hours of these cows can cover 1 ~ t.
Method: Press each cow for working hoursstart timeFrom small to large sorting, and then in 1 ~ t timeStarting time in the unanimous moment, find out the cow that can cover the time at the beginning and end the latest time.
Note the pit points of this question: This question is given time instead of interval endpoints, so except that the start time of the first cow must be 1, the start time of the first Ichi cow then is the end of the i-1 head cow+ 1.
For example, for samples:
4 10
1 3
3 5
4 7
8 10
The answer is to select [1 3] [4 7] [8 10]
First of all, 1 ~ T time1 time is the beginning of the moment that is not covered, only [1 3] can be covered.
and then4 The beginning of the moment when it is not covered, only [4 7] can cover 4 times
Last8 The beginning of the moment when the moment is not covered, only [8 10] can cover 8 times
At this time, 1 ~ T is overwritten and ended.
So the final answer is 3.
java code:
import java.io.*;
import java.util.*;
import java.math.*;
public class Main{
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
static class node implements Comparable<node>{
// Customized class, save the start and end time
int l, r; // need to be sorted according to the start time, so the Comparable interface is implemented to customize sorting.
node(int l, int r){
this.l = l;
this.r = r;
}
public int compareTo(node b) {
return this.l - b.l;
}
}
static node[] arr = new node[25005];
static int Int(String s){
return Integer.parseInt(s);
}
public static void main(String[] args) throws Exception{
int T, n;
String[] s = in.readLine().split(" ");
n = Integer.parseInt(s[0]);
T = Integer.parseInt(s[1]);
for(int i = 0; i < n; i++){
String[] s1 = in.readLine().split(" ");// Read in
arr[i] = new node(Int(s1[0]), Int(s1[1]));
}
Arrays.sort(arr, 0, n - 1); // Sorting
int flag = 0, res = 0, start = 1; // // The beginning of the first time is the beginning of the unscrumped interval
for(int i = 0; i < n; i++){
int j = i;
int r = -1000;
if(arr[0].l > 1){
break;
}
while(j < n &&(start != 1 &&arr[j].l <= start+1|| start == 1 && arr[j].l == 1)){
r = Math.max(r, arr[j].r);
j ++;
}
res ++;
if(r < start){
// If R <START explains that there is no qualified interval. Direct Bream output-1
break;
}
if(r >= T ){
// If R> = t indicates that the interval has been completely covered, BREAK output answer
flag = 1;
break;
}
start = r; // Update the start time
i = j - 1; // 0 ~ J-1 has traveled through the interval and skipped directly.
}
if(flag != 1) res = -1;
out.write(Integer.toString(res));
out.flush();
}
}
Huffman tree is also a classic manifestation of greedy thoughts. Given N leaf nodes, and use these N leaf nodes to construct a binary tree. The Huffman tree is the smallest binary tree with power path.
huffman tree detailed explanation video:
https://www.bilibili.com/video/BV18t411U7bj/?spm_id_from=333.788.videocard.4
Huffman Tree Features: The greater the leaf node of the weight, the closer the root node, and the smaller the leaf node, the farther the root node of the root node.
Constructing Huffman tree:
In order to ensure the minimum length of the right to obtain, we have to merge two minimum leaf nodes each time.
Example:POJ 3253
Title: John wants to cut a piece of wooden board into N pieces. Without cutting it once, the cost of the current cutting of the current cutting of the currently cut is to the minimum price.
Converted into a huffman tree, John’s final wood block length is the leaf node. So just find a huffman tree and find the length of the right path.
Use the priority queue to merge two minimum nodes at a time.
code:
import java.io.*;
import java.util.*;
import java.math.*;
public class Main{
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
static int Int(String s){
return Integer.valueOf(s);
}
public static void main(String[] args) throws Exception{
int n = Int(in.readLine());
PriorityQueue<Integer> heap = new PriorityQueue<Integer>(); // small roots pile
while(n --> 0){
heap.add(Int(in.readLine()));
}
long res = 0;// The answer is very large, deposit with long
while(heap.size() != 1)
{
int min = heap.poll() + heap.poll();
res += min;
heap.add(min);
}
out.write(res + "");
out.flush();
}
}
There are many other types of greedy problems, and the text is not listed one by one. It is mainly to be greedy to be greedy. question.