greedy

Greedy can be said to be the most easily understood algorithm idea: decompose the whole problem into multiple steps, and in each step, select the optimal scheme of the current step until the end of all steps; In each step, the impact on the subsequent steps is not considered, and the previous choices will not be changed in the subsequent steps. To put it simply, its idea is to "look at it step by step" and "be short-sighted".

Although the greedy method may not get the optimal solution, it is simple and easy to program. Therefore, if a problem is determined that the optimal solution can be obtained by greedy method, it should be used.

The problems solved by greedy method need to meet the following characteristics:

• Optimal substructure properties. When the optimal solution of a problem contains the optimal solution of its subproblem, it is said that the problem has the property of optimal substructure, and it is also said that the problem satisfies the optimality principle. In other words, it can be extended from local optimization to global optimization.
• Greedy choice nature. The global optimal solution of the problem can be obtained through a series of local optimal choices.

Greedy algorithm has no fixed algorithm framework. The key is how to choose greedy strategy.

The so-called greedy strategy must have no aftereffect, that is, the process after a certain state will not affect the previous state, but only related to the current state. In addition, the greedy method is used in "although it's not the best, it's good. I'm satisfied!" On some difficult problems, such as the traveling salesman problem, it is difficult to obtain the optimal solution. However, good approximate solutions can often be obtained by greedy method. If the optimal solution is not necessarily required, the greedy result is also a very good scheme.

Activity arrangement

Greedy strategy: select the earliest end time

1. It conforms to the property of optimal substructure. The # 1st # activity selected must be in an optimal solution; Similarly, the # 2nd # activity and # 3rd # activity selected... Are also in this optimal solution.
2. It is in line with the nature of greedy choice. Every step of the algorithm uses the same greedy strategy.

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100
struct record {
    int s, e;    //Define the start and end time of the activity: start, end
} r[MAXN];
bool cmp(const record& a, const record& b)
{ return a.e < b.e;  }
int main(){
    int n;
     while(1){
        cin >> n;    //Enter n activities
        if(n == 0)   break;  // End when n==0
        for(int i=0; i<n; i++)  //Enter the start and end time of each activity
            cin >> r[i].s >> r[i].e;
        sort(r, r + n, cmp);  // Sort: sort by end time
        int count = 0;         //Count the number of activities
        int lastend = -1;
        for(int i=0; i<n; i++) // Greedy Algorithm 
            if(r[i].s >= lastend) {//Last start time > = last end time
                count++;
                lastend = r[i].e; //Record the termination time of the previous activity
            }
        cout << count << endl; //Number of output activities
    }
    return 0;
}

Interval covering problem

• Sort each segment incrementally according to the left endpoint.
• Let the covered interval be [L, R]. In the remaining line segments, find all the line segments with the left end point less than or equal to ﹤ R and the largest right end point, add this line segment to the covered interval, and update the [L, R] value of the covered interval.
• Repeat step # 2 until all sections are covered.

Optimal loading problem (classical 0-1 knapsack problem)

First, sort the liquid medicine according to the concentration from small to large. If the concentration of liquid medicine is not greater than ， w%, add it. If the concentration of liquid medicine is greater than ， w%, calculate the total concentration after mixing, and add it if it is not greater than ， w%. Otherwise, end the judgment.   

Multi machine scheduling problem

      

The greedy strategy for solving the multi machine scheduling problem is to give priority to the job with the longest processing time, that is, assign the job with the longest processing time to the first idle machine. Give priority to jobs with long processing time, so as to obtain the shortest processing time as possible on the whole.

1. If n ≤ m, the required time is the longest processing time of n ﹐ jobs, ﹐ t.
2. If # n > m, first sort # n # jobs according to the processing time, and then allocate jobs to idle machines in order.

Question 1 turn the coin

sample input

**********
o****o****

sample output

5

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s1 = scanner.next();
        String s2 = scanner.next();
        char a1[] = s1.toCharArray();
        char a2[] = s2.toCharArray();
        int flag = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (a1[i] != a2[i]) {
                if (a1[i + 1] == '*') {
                    a1[i + 1] = 'o';
                } else {
                    a1[i + 1] = '*';
                }
                flag++;
            }
        }
        System.out.println(flag);
    }
}

Question 2 defense

sample input

1 2
4
2 8
101

sample output

B2
A1
B1
E

After verification, A increases the fastest from small to large and B increases the fastest from large to small (it's best to program and compile data by yourself. It's easy to be confused by written calculation)

import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n1 = scanner.nextInt();
        int n2 = scanner.nextInt();
        int[] A = new int[n1 + 1];
        int[] B = new int[n2 + 1];
        for (int i = 1; i <= n1; i++) {
            A[i] = scanner.nextInt();
        }
        for (int i = 1; i <= n2; i++) {
            B[i] = scanner.nextInt();
        }
        String s = scanner.next();
        char[] C = s.toCharArray();
        for (int i = 0; i < C.length; i++) {
            if (C[i] == '0') {
                int id = 1;
                int flag = A[1];
                for (int j = 1; j <= n1; j++) {
                    if (A[j] < flag) {
                        id = j;
                        flag = A[j];
                    }
                }
                A[id] = Integer.MAX_VALUE;//Set to maximum
                System.out.println("A" + id);
            } else {
                int id = 1;
                int flag = B[1];
                for (int j = 1; j <= n2; j++) {
                    if (B[j] > flag) {
                        id = j;
                        flag = B[j];
                    }
                }
                B[id] = Integer.MIN_VALUE;//Set to minimum
                System.out.println("B" + id);
            }
        }
        System.out.println("E");
    }
}

Question 3: maximum and minimum common multiples

sample input

9

sample output

504

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long ans;
        if (n <= 2) ans = n;
        else if (n % 2 != 0)
            ans = n * (n - 1) * (n - 2);
        else {
            if (n % 3 != 0) ans = n * (n - 1) * (n - 3);
            else ans = (n - 1) * (n - 2) * (n - 3);
        }
        System.out.println(ans);
    }
}

Question 4 souvenir grouping

sample input

100
9
90
20
20
30
50
60
70
80
90

sample output

6

It's easy to be greedy

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int w = scanner.nextInt();
        int n = scanner.nextInt();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }
        Arrays.sort(a);
        int ans = 0;
        for (int i = 1, j = n; i <= j; ) {
            if (a[i] + a[j] <= w) {
                i++;
                j--;
                ans++;
            } else {
                j--;
                ans++;
            }
        }
        System.out.println(ans);
    }
}

Question 5 happy driver (ordinary greedy problem)

sample input

5 36
99 87
68 36
79 43
75 94
7 35

sample output

71.3

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int w = scanner.nextInt();
        Cmp[] cmp = new Cmp[n];
        for (int i = 0; i < n; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            double temp = (double) b / a;
            cmp[i] = new Cmp(a, b, temp);
        }
        Arrays.sort(cmp, (o1, o2) -> {
            if (o1.temp - o2.temp >= 0) {
                return -1;
            } else {
                return 1;
            }
        });
        int ans = 0;
        double value = 0;
        for (int i = 0; i < n; i++) {
            if (cmp[i].a + ans > w) {
                value = value + (w-ans)*(cmp[i].temp);
                break;
            }else{
                value = value + cmp[i].b;
                ans = ans + cmp[i].a;
            }
            if (ans > w) break;
        }
        System.out.println(String.format("%.1f",value));
    }
}

class Cmp {
    int a;
    int b;
    double temp;

    Cmp(int a, int b, double temp) {
        this.a = a;
        this.b = b;
        this.temp = temp;
    }
}

It's time to pick up the collection. The object array is really hard