贪心专题讲解
定义：贪心算法（greedy algorithm [8] ，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。
那么，根据实际刷题经验来看，贪心算法就是根据局部最优解能得到全局最优解。其实通常贪心的难点在于靠自己去根据经验判断，猜测是否可以这样来做。如果自己可以迅速证明自己想的局部贪心策略在全局也会是最优的，那么就可以直接快速做。然而，有的时候自己根据贪心的策略做出来了某个题，但是实际上自己没法用公式或者数学推导证明，也是很有可能的，所以更多的贪心的题通常是根据经验去做。
P1223 排队接水
题目描述
有n 个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n 个人排队的一种顺序，使得n 个人的平均等待时间最小。
输入格式
第一行为一个整数n。
第二行n 个整数，第 i 个整数Ti 表示第i 个人的等待时间 Ti。
输出格式
输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。
样例
样例输入
10 56 12 1 99 1000 234 33 55 99 812
样例输出
3 2 7 8 1 4 9 6 10 5 291.90
提示
结论：因此只有当越小的排在越前面的时候，才会使得整体等待时间耗费最少，而平均等待耗费时间跟整体等待耗费时间成正比，因此也就能使得平均等待耗费时间最少。证明完毕。
代码附上：
在这里题还要注意两点：
- 两位浮点小数输出格式
System.out.printf("%.2f%n",res/n);
- 用二维数组记录对应的下标，因为题目要求我们输出排队的下标顺序，且是从1开始，因此要记得在数组下标对应的加1
import java.io.*; import java.util.Arrays; import java.util.Comparator; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(br.readLine().replaceAll(" ", "")); String[] s = br.readLine().split(" "); int[][] arr = new int[n][2]; for (int i = 0; i < n; i++) { arr[i][0] = Integer.parseInt(s[i]); arr[i][1] = i; } Arrays.sort(arr, (o1, o2) -> { if (o1[0] != o2[0]) { return o1[0] - o2[0]; } else { return o1[1] - o2[1]; } }); double res = 0; for (int i = 0 ; i < n; i++) { System.out.print(arr[i][1] + 1 + " "); res += arr[i][0] * (n - i - 1); } System.out.println(); System.out.printf("%.2f%n",res/n); bw.close(); br.close(); } }
P1803 线段覆盖
题目背景
题目描述
输出格式
一个整数最多参加的比赛数目。
样例
样例输入
3 0 2 2 4 1 3
样例输出
2
提示
import java.io.*; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(br.readLine().replaceAll(" ", "")); int[][] arr = new int[n][2]; for (int i = 0; i < n; i++) { String[] s = br.readLine().trim().split(" "); arr[i][0] = Integer.parseInt(s[0]); arr[i][1] = Integer.parseInt(s[1]); } Arrays.sort(arr, (o1, o2) -> { return o1[1] - o2[1]; }); int res = 0; int idx = 0; int mi = 0; while (idx < n) { if (arr[idx][0] >= mi) { res++; mi = arr[idx][1]; } idx++; } bw.write(res + "\n"); bw.flush(); bw.close(); br.close(); } }
P1090 [NOIP2004 提高组] 合并果子
题目描述
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
样例
样例输入
3 1 2 9
样例输出
15
提示
代码如下：
import java.io.*; import java.util.PriorityQueue; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(br.readLine().trim()); String[] s = br.readLine().trim().split(" "); int[] arr = new int[n]; PriorityQueue<Integer> q = new PriorityQueue<>(); for (int i = 0 ; i < n ; i++) { arr[i] = Integer.parseInt(s[i]); q.add(arr[i]); } int res = 0; while (q.size() >= 2) { int a = q.poll(); int b = q.poll(); res += (a + b); q.add(a + b); } bw.write(res + "\n"); bw.flush(); bw.close(); br.close(); } }
p3817 小A的糖果
题目描述
输出格式
输出一行一个整数，代表最少要吃掉的糖果的数量。
样例
样例输入
3 3 2 2 2
样例输出
1
样例
样例输入
6 1 1 6 1 2 0 4
样例输出
11
样例
样例输入
5 9 3 1 4 1 5
样例输出
0
提示
样例输入输出 1 解释
吃掉第 2 盒中的一个糖果即可。
样例输入输出 2 解释
第 2 盒糖吃掉6 颗，第 4 盒吃掉 2 颗，第 6 盒吃掉 3 颗。
数据规模与约定
import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); String[] s1 = br.readLine().trim().split(" "); int n = Integer.parseInt(s1[0]); int x = Integer.parseInt(s1[1]); String[] s2 = br.readLine().trim().split(" "); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(s2[i]); } long res = 0; if (arr[0] > x) { res += arr[0] - x; arr[0] = x; } for (int i = 1; i < n; i++) { if (arr[i] + arr[i - 1] > x) { res += (arr[i] + arr[i - 1] - x); arr[i] = x - arr[i - 1]; } } bw.write(res + "\n"); bw.flush(); bw.close(); br.close(); } }
总结一下
- 贪心算法适用范围有限，仅仅适用于当前策略在局部最优且可以推广至全局最优时，才可以采取贪心策略。
- 如果能用贪心算法策略且同时可以用动态规划做的时候，贪心算法在很多时候会能比动态规划的时间复杂度要低或者相等，但是众所周知越是能够最优的往往适用范围就有限。
- 有的时候贪心的题自己也没法第一时间证明是否是正确的，可以大胆猜想去做，如果失败了，就可以举特例去反推。当然贪心只是一种策略，还会需要结合一些其他的数据结构或者数据处理才能解题，比如「排序」、「优先队列」。
