大家好，这里是祁十一！Now，我想给大家讲一下贪心算法。贪心法，顾名思义，就是贪多、贪好。那么，让我们来一起看一下贪心算法是怎么“贪婪无言”的吧！ 

目录

1、什么是贪心算法？

2、怎么理解贪心算法？

【蓝桥算法训练】最大最小公倍数

3、算法就要多加练习！

【蓝桥算法训练】排队接水2

1、什么是贪心算法？

        贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择 。

2、怎么理解贪心算法？

        先举个简单的例子！

【蓝桥算法训练】最大最小公倍数

【题目】已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。输入一个正整数N。输入一个正整数N。输出一个整数，表示你找到的最小公倍数。

说实话，再没学贪心之前，我是这样写的（满怀信心的我在看到运行超时的一瞬间直呼救命！）

import java.util.*;public class Main{public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();Random r = new Random();int a=r.nextInt(n);int b=r.nextInt(n);int c=r.nextInt(n);LCM(a,b,c);}public static void LCM(int a,int b,int c){ int k=getMax(a,b,c); for (int i=k;;i++){ if(i%a==0 && i%b==0 && i%c==0){ System.out.println(i); break;} }}public static int getMax(int a ,int b,int c){int []arr={a,b,c};Arrays.sort(arr) ;return arr[2];}}

        在重新读了三遍题目以后，我发现了有一个突破点！要求最大的最小公倍数，当三个数互为质数的时候且乘起来最大不就可以啦！所以，我们用贪心的思维（咱搞就要搞最大！），直接考虑取后三个数（n、n-1、n-2）。注意n的范围，代码中已标出原因。

import java.util.*;public class Main{public static void main(String[] args) {Scanner sc=new Scanner(System.in);long n=sc.nextLong(); //n如果小于2，直接就不用求了if(n<=2){System.out.println(n);}if(n>2){if(n%2!=0)//当n为奇数的时候，n-2也是奇数，三数相乘输出这个数为最大公倍数System.out.println(n*(n-1)*(n-2)); //当n为偶数，n和n-2有约数2，再向前推一个，n与n-3相差3，判断一下能不能被3整除if(n%3==0&&n%2==0) //若能整除，直接整体向前移动，变成“奇偶奇”形式System.out.println((n-1)*(n-2)*(n-3));if(n%3!=0&&n%2==0)//若不能整除，输出即可System.out.println(n*(n-1)*(n-3));}}}

3、算法就要多加练习！

【蓝桥算法训练】排队接水2

【题目】有N个人排队到M个水龙头去打水，他们装满水桶的时间T1,T2……Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的总时间最少？

（输入）第1行：两个整数n和m，n表示人的个数，m表示水龙头的个数；第2行，n个数分别表示n个人装水的时间。（输出）一个整数，表示总花费的最少时间。

        这个题猛得一看很奇怪，因为打水再怎么打要都是一个人接完另一个上，时间好像都是一样的啊，仔细一看样例（如下）。

输入输出6 2
5 4 6 2 1 740

        好像明白了什么又好像什么也没明白，那笔一写一画，我知道了，他的过程可能是这样的：

        n=6，且排完序为1、2、4、5、6、7；m=2，水龙头A和水龙头B。

水龙头A水龙头B1（1）2（2）4（1+4）5（2+5）6（1+4+6）7（2+5+7）A总1+5+11=17B总2+7+14=23总和为40

        思路有了，那么代码如下：

import java.util.*;public class Main{public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); int[] watertime=new int[n]; int[] num=new int[m]; int sum=0; //输入每个人接水的时间 for(int i=0;i