贪心类问题是很常见的考点，贪心算法更重要的是一种贪心的思想，它追求的是当前最优解，从而得到全局最优解。贪心类问题基本上算是必考题型之一，它能更好的考察出学生的思维能力以及对问题的分析能力，很多学校的出题人都非常爱出贪心类的题目。

贪心算法的定义：

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

贪心可以很简单，简单到让所有人一眼就能看出来该怎么做。贪心也可以很难，难到让你没办法去证明这样贪心的正确性。所以要想解决贪心这类问题，主要还是看你的悟性，看你对题目的分析能力如何，下面我们举例说明。

例子1：地上有3张纸币，分别是5元、1元和10元，问你只能拿一张，最多能拿多少钱？
解析：很明显，10元。
例子2：地上有n张纸币，有1元的，有5元的，还要10元的，问你只能拿一张，最多能拿多少钱？
解析：很明显，还是10元。
例子3：地上有很多纸币，有a张1元的，有b张5元的，还要c张10元的，问你从中拿x张，最多能拿多少钱？
解析：大家应该都能想到，肯定是优先拿10元的，如果10元的拿完了，再拿5元的，最后才会拿1元的。这就是贪心的思想，所以贪心其实是很容易想到的。
例子4：有n个整数构成的集合，现在从中拿出x个数来，问他们的和最大能是多少？
解析：相信大家都能想到，优先拿大的，从大到小一个个拿，这样组成的和最大。那么在解决这个问题之前，我们需要先排序，从大到小的排好序，然后将前x个数的和累加起来就是答案。

从上面几个例子中，相信大家对贪心已经有了初步的了解。我们使用贪心的时候，往往需要先按照某个特性先排好序，也就是说贪心一般和sort一起使用。

喝饮料
题目描述：
商店里有n中饮料，第i种饮料有mi毫升，价格为wi。
小明现在手里有x元，他想吃尽量多的饮料，于是向你寻求帮助，怎么样买才能吃的最多。
请注意，每一种饮料都可以只买一部分。
输入描述：
有多组测试数据。
第一行输入两个非负整数x和n。
接下来n行，每行输入两个整数，分别为mi和wi。
所有数据都不大于1000。
x和n都为-1时程序结束。
输出描述：
请输出小明最多能喝到多少毫升的饮料，结果保留三位小数。
输入样例#:
233 6 
6 1
23 66
32 23
66 66
1 5
8 5
-1 -1
输出样例#:
136.000
题目来源：
DreamJudge 1478

题目解析：通过分析之后我们可以发现，小明想要喝尽量多的饮料的话，肯定优先选择性价比最高的饮料喝，也就是说1毫升的价格最低的饮料先喝，那么我们就需要去比较，每种饮料1毫升的价格是多少。然后按照这个单价从低到高依次排序，然后一个一个往后喝，这样可以保证小明能喝到最多的饮料。

参考代码

#include <bits/stdc++.h>  
using namespace std;  
  
struct node {  
    double w, m;  
}p[1005];  
bool cmp(node a, node b) ...

练习题目

DreamJudge 1307 组队刷题
DreamJudge 1347 To Fill or Not to Fill