贪心

贪心（Greedy）可以说是最容易理解的算法思想：把整个问题分解成多个步骤，在每个步骤，都选取当前步骤的最优方案，直到所有步骤结束；在每一步，都不考虑对后续步骤的影响，在后续步骤中也不再回头改变前面的选择。简单地说，其思想就是“走一步看一步”、“目光短浅”。

虽然贪心法不一定能得到最优解，但是它思路简单、编程容易。因此，如果一个问题确定用贪心法能得到最优解，那么应该使用它。

贪心法求解的问题，需要满足以下特征：

• 最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。也就是说，从局部最优能扩展到全局最优。
• 贪心选择性质。问题的整体最优解可以通过一系列局部最优的选择来得到。

贪心算法没有固定的算法框架，关键是如何选择贪心策略。

所谓贪心策略，必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。另外，把贪心法用在“虽然不是最好，但是还不错，我表示满意！”的某些难解问题上，例如旅行商问题，是很难得到最优解的。但是用贪心法常常能得到不错的近似解。如果不一定非要求得最优解，那么贪心的结果，也是很不错的方案。

活动安排问题

贪心策略：选择最早结束时间

1. 它符合最优子结构性质。选中的第 1 个活动，它一定在某个最优解中；同理，选中的第 2 个活动、第 3 个活动……也同样在这个最优解中。
2. 它符合贪心选择性质。算法的每一步都使用了相同的贪心策略。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100
struct record {int s, e;    //定义活动的起止时间： 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;    //输入n个活动if(n == 0)   break;  // n==0时结束for(int i=0; i<n; i++)  //输入每个活动的起止时间cin >> r[i].s >> r[i].e;sort(r, r + n, cmp);  // 排序：按结束时间排序int count = 0;         //统计活动个数int lastend = -1;for(int i=0; i<n; i++) // 贪心算法if(r[i].s >= lastend) {//后一个起始时间 >= 前一个终止时间count++;lastend = r[i].e; //记录前一个活动终止时间}cout << count << endl; //输出活动个数}return 0;
}

 区间覆盖问题

• 把每个线段按照左端点递增排序。
• 设已经覆盖的区间是 [L, R] ，在剩下的线段中，找所有左端点小于等于 R，且右端点最大的线段，把这个线段加入到已覆盖区间里，并更新已覆盖区间的 [L, R]值。
• 重复步骤 2，直到区间全部覆盖。

最优装载问题 （经典0-1背包问题）

         先对药水按浓度从小到大排序，药水的浓度不大于 w% 就加入，如果药水的浓度大于 w%，计算混合后总浓度，不大于 w% 就加入，否则结束判断。  

多机调度问题

      

求解多机调度问题的贪心策略是：最长处理时间的作业优先，即把处理时间最长的作业分配给最先空闲的机器。让处理时间长的作业得到优先处理，从而在整体上获得尽可能短的处理时间。

1. 如果 n≤m，需要的时间就是 n 个作业当中最长处理时间 t。
2. 如果 n>m，首先将 n 个作业按处理时间从大到小排序，然后按顺序把作业分配给空闲的机器。

第一题 翻硬币

样例输入

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

样例输出

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);}
}

第二题 防御力

样例输入

1 2
4
2 8
101

样例输出

B2
A1
B1
E

 验证之后 是A从小到大、B从大到小增加 最快（最好编程自己编数据试试，笔算很容易懵逼）

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;//设置成最大值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;//设置成最小值System.out.println("B" + id);}}System.out.println("E");}
}

第三题  最大最小公倍数

样例输入

9

样例输出

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);}
}

第四题 纪念品分组

样例输入

100
9
90
20
20
30
50
60
70
80
90

样例输出

6

 尺取+贪心 很容易

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);}
}

 第五题 快乐司机（普通的贪心问题）

样例输入

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

样例输出

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;}
}

该把集合捡起来了，对象数组真费劲