一、什么是贪心算法？

贪心是用来解决一类最优化问题，并希望由局部最优策略来推得全局最优结果的算法思想。贪心算法适用的问题一定满足最优子结构性质，即一个问题的最优解可以由它的子问题的最优解有效地构造出来。

玛卡你废话少说，直接上代码吧

得嘞~

二、简单贪心

①月饼问题

   问题描述：   您是个大老板，手里有一堆月饼。现给定所有种类的月饼的库存量、总售价以及市场的最大需求量，试计算可以获得的最大收益是多少

      注意：销售时允许取出一部分库存。样例给出的情形是这样的： 假如有三种月饼，其库存量分别为18、15、10万吨，总售价分别为75、72、45亿元。如果市场的最大需求量只有(20万吨，那么最大收益策略应该是卖出全部15万吨第二种月饼以及5万吨第三种月饼，获得72+45/2=94.5(亿元)。

 输入格式：每个输入包含1个测试用例。每个测试用例先给出一个不超过1000的正整数N表示月用饼的种类数以及不超过500(以万吨为单位)的正整数D表示市场最大需求量； 随后一行给出N个正数表示每种月饼的库存量(以万吨为单位)； 最后一行给出N个正数表示每种月饼的总售价(以亿元为单位)。数字间以空格分隔。
输出格式：对每组测试用例，在一行中输出最大收益，以亿元为单位精确到小数点后两位。
输入样例：3   20
                 18  15  10
                 75  72  45
输出样例：94.50

 分析：步骤1：总是选择单价最高的月饼出售，可以获得最大的利润”的策略。因此，对每种月饼，都根据其库存量和总售价来计算出该种月饼的单价。之后，将所有月饼按单价从高到低排序。
从单价高的月饼开始枚举。
①如果该种月饼的库存量不足以填补所有需求量，则将该种月饼全部卖出，此时需求量减少该种月饼的库存量大小，收益值增加该种月饼的总售价大小。
②如果该种月饼的库存量足够供应需求量，则只提供需求量大小的月饼，此时收益值增加当前需求量乘以该种月饼的单价，而需求量减为0。这样，最后得到的收益值即为所求的最大收益值。

#include<stdio.h>
#include<algorithm>
using namespace std;
struct mooncake{ 
    double store ;//库存量
    double sell;//总售价 
    double price;// 单价/
}cake[1010];
 
bool cmp(mooncake a,mooncake b){//按单价从高到低排序
    return a.price>b.price;
}
int main() {
    int n;
    double D;
    scanf("%d%lf",&n,&D);
    for(int i=0;i<n;i++){
        scanf("%lf",&cake[i].sell);
    }
    for(int i = 0;i < n;i++) {
        scanf("%lf",&cake[i]. sell);
        cake[i].price=cake[i].sell/cake[i].store;//计算单
    }
    sort(cake,cake+n,cmp);//按单价从高到低排序
    double ans=0;//收益
    for(int i=0;i < n;i++) {
        if(cake[i]. store<=D) {//如果需求量高于月饼库存量
            D -=cake[i].store; //第i种月饼全部卖出
            ans+=cake[i].sell;
    }else { //如果月饼库存量高于需求量
        ans+=cake[i].price*D;//只卖出剩余需求量的月饼break;
        break;
	    }
    }
    printf("%.2f\n", ans);
    return 0;
}

②最优装箱问题

   问题描述：   有n个箱子需要装上一艘轮船，已知第i个箱子的重量为wi，轮船的载重为W。问在不超过轮船载重的前提下，最多能把多少个箱子装上轮船。

 输入格式：

第一行两个正整数n、W（1≤n≤105、1≤W≤107），分别表示箱子个数和轮船载重。

第二行n个正整数wi（1≤wi≤107），表示n个箱子的重量。

输出格式：输出两个整数，分别表示能装上轮船的箱子个数和总重量，用空格隔开。
输入样例：5 11

                  7 2 9 1 11
输出样例：3 10

 分析：能将重量分别为7、2、1的箱子装上轮船（此时箱子个数最多），总重量为10。还是先考虑排序。

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100010;
int a[MAXN];
 
int main() {
    int n, maxW;
    scanf("%d%d", &n, &maxW);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a + n);
    int num = 0, sum = 0;
    for (int i = 0; i < n; i++) {
        if (sum + a[i] <= maxW) {
            num++;
            sum += a[i];
        } else {
            break;
        }
    }
    printf("%d %d", num, sum);
    return 0;
}

③整数配对问题

   问题描述：有两个正整数集合S、T，其中S中有n个正整数，T中有m个正整数。定义一次配对操作为：从两个集合中各取出一个数a和b，满足a∈S、b∈T、a≤b，配对的数不能再放回集合。问最多可以进行多少次这样的配对操作。

 输入格式：

第一行 两个正整数n、m（1≤n≤104、1≤m≤104），分别表示S和T中正整数的个数。

第二行 n个正整数ai（1≤ai≤105），表示S中的n个正整数。

第三行 m个正整数bi（1≤bi≤105），表示T中的m个正整数。

输出格式：输出一个整数，表示最多的配对操作次数。
输入样例：3 3

                 2 5 3   

                 3 3 4
输出样例：2

 分析：2与其中一个3配对，3与另一个3配对，5无法和4配对。因此最多配对两次。

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 10000;
int a[MAXN], b[MAXN];
 
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d", &b[i]);
    }
    sort(a, a + n);
    sort(b, b + m);
    int counter = 0;
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (a[i] <= b[j]) { //在排序好之后，依次比较ab的大小，相同则b再加
            counter++;    //counter计数的前提是出现a<b的关系
            i++;
            j++;
        } else {
            j++;
        }
    }
    printf("%d", counter);
    return 0;
}

④最大组合整数

   问题描述：现有0~9中各个数的个数，将它们组合成一个整数，求能组合出的最大整数。

 输入格式：

在一行中依次给出0~9中各个数的个数（所有个数均在0~100之间）。数据保证至少有一个数的个数大于0。

输出格式：输出一个整数，表示能组合出的最大整数。
输入样例：1 0 2 0 0 0 0 0 0 1
输出样例：9220

 分析：存在1个0、2个2、1个9，因此能组合出的最大整数是9220，显然输出的数越靠后越大，肯定要把大的数放前面

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 10;
int cnt[MAXN];
 
int main() {
    for (int i = 0; i < MAXN; i++) {
        scanf("%d", &cnt[i]);
    }
    bool isZero = true;
    for (int i = MAXN - 1; i >= 0; i--) {
        if (i > 0 && cnt[i] > 0) { //如果该数字不为空，即有数字
            isZero = false;
        }
        if (!isZero) {
            for (int j = 0; j < cnt[i]; j++) { //有数字即输出
                printf("%d", i);
            }
        }
    }
    if (isZero) {
        printf("0");
    }
    return 0;
}

三、区间贪心

 ①区间不相交问题

   问题描述：给定n个开区间，从中选择尽可能多的开区间，使得这些开区间两两没有交集。

 输入格式：

第一行为一个正整数n（1≤n≤104），表示开区间的个数。

接下来n行，每行两个正整数xi、yi（0≤xi≤105、0≤yi≤105），分别表示第i个开区间的左端点和右端点。

输出格式：输出一个整数，表示最多选择的开区间个数。​​​​​​​
输入样例：4

                  1 3

                  2 4

                  3 5

                  6 7
输出样例：3

 分析： 先将区间左端点进行排序，某段选右端点小于下一段的左端点，即不相交，再把下一段的左端点改成该段的右端点，最多选择(1,3)、(3,5)、(6,7)三个区间，它们互相没有交集。

#include <cstdio>
#include <algorithm>
using namespace std;
 
const int MAXN = 10000;
 
struct Interval {
    int l, r;
} interval[MAXN];
 
bool cmp(Interval a, Interval b) {
    if (a.l != b.l) {
        return a.l > b.l;
    } else {
        return a.r < b.r;
    }
}
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &interval[i].l, &interval[i].r);
    }
    sort(interval, interval + n, cmp);
    int num = 1, lastL = interval[0].l;
    for (int i = 1; i < n; i++) {
        if (interval[i].r <= lastL) {
            lastL = interval[i].l;
            num++;
        }
    }
    printf("%d", num);
    return 0;
}

  ②区间选点问题

   问题描述：给定n个闭区间，问最少需要确定多少个点，才能使每个闭区间中都至少存在一个点。

 输入格式：

第一行为一个正整数n（1≤n≤104），表示闭区间的个数。

接下来n行，每行两个正整数xi、yi（0≤xi≤105、0≤yi≤105），分别表示第i个闭区间的左端点和右端点。

输出格式：输出一个整数，表示最少需要确定的点的个数。​​​​​​​
输入样例：3

                  1 4

                   2 6

                   5 7
输出样例： 2

 分析： 求相交的部分，至少需要两个点（例如3和5）才能保证每个闭区间内都有至少一个点。

#include <cstdio>
#include <algorithm>
using namespace std;
 
const int MAXN = 10000;
 
struct Interval {
    int l, r;
} interval[MAXN];
 
bool cmp(Interval a, Interval b) {
    if (a.l != b.l) {
        return a.l > b.l;
    } else {
        return a.r < b.r;
    }
}
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &interval[i].l, &interval[i].r);
    }
    sort(interval, interval + n, cmp);
    int num = 1, lastL = interval[0].l;
    for (int i = 1; i < n; i++) {
        if (interval[i].r < lastL) {//如果两区间相交，则左右端点融合
            lastL = interval[i].l;
            num++;
        }
    }
    printf("%d", num);
    return 0;
}

总的来说，就是自己先想好什么策略最优，然后去验证可行性，勇敢去想吧！