一、基本概念
       所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
       贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
       所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
二、基本思路
       1.建立数学模型来描述问题。
       2.把求解的问题分成若干个子问题。
       3.对每一子问题求解，得到子问题的局部最优解。
      4.把子问题的解局部最优解合成原来解问题的一个解。
三、适用问题 
       贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
四、实现框架
      从问题的某一初始解出发；
       while （能朝给定总目标前进一步）
       {
            利用可行的决策，求出可行解的一个解元素；
       }
      由所有解元素组合成问题的一个可行解；
五、贪心策略的选择
        因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。


1)【例1】排队打水问题
       有N个人排队到R个水龙头去打水，他们装满水桶的时间为T1，T2，…，Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的时间最少？
【算法分析】
    由于排队时，越靠前面的计算的次数越多，显然越小的排在越前面得出的结果越小（可以用数学方法简单证明，这里就不再赘述），所以这道题可以用贪心法解答，基本步骤：
     (1)将输入的时间按从小到大排序；
     (2)将排序后的时间按顺序依次放入每个水龙头的队列中；     
     (3)统计，输出答案。
【样例输入】
      4  2                      //4人打水，2个水龙头
      2  6  4  5              //每个打水时间

问题分析：
这题说“显然越小的排在越前面，得出的结果越小”，是草率的；
可以对比另一道题目，最佳调度问题 //blog.sina.com.cn/s/blog_13bd4d96a0102yo86.html
可以发现，其他条件和求解，都几乎一样，只有一个地方不同：本题要算上等待时间，那一题不用。
所以，“显然”只是对“只有一个水龙头”的情况下，是显然的；这样两题就可以得到统一；
在超出两个以上水龙头时，要证明它并不容易，（否则那一题也“很容易”证明了，实际上那样解就是错的），在接水问题上，是因为等待时间有累积性，这样随着ti而增加的离散化会非常大，从而令“不正确的可能性”得以忽略。
这只是说明一个问题：贪心不是一种完整的算法，只是一种“妥协”算法。

以下是本题的题解：
#include "bits/stdc++.h"
using namespace std;
int s[1000],a[1000];
int main(){
    int n,r;
    cin>>n>>r;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);

       int j=0,minx=0;
       for (int i=1;i<=n;++i)                           //用贪心法求解
    {
      j++; if (j==r+1) j=1;                           //前r个人为一组，第r+1个人回到第一个水龙
      s[j]+=a[i];                                   //加上等待时间
      minx+=s[j];
    }
   cout<<minx;                                //输出解答
}

2) 2010NOIP openjudge:*接水问題
    学校里有一个水房，水房里一共装有 m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为 1。
    现在有 n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从 1 到 n 编号，i号同学的接水量为 wi。接水开始时，1 到 m 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学 j 完成其接水量要求 wj后，下一名排队等候接水的同学 k 马上接替 j 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即 j 同学第 x 秒结束时完成接水，则 k 同学第 x+1 秒立刻开始接水。 若当前接水人数 n’不足 m，则只有 n’个龙头供水，其它 m-n’个龙头关闭。
    现在给出 n 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。
输入
    第 1 行2 个整数 n 和 m，用一个空格隔开，分别表示接水人数和龙头个数。
    第 2 行 n 个整数 w1、w2、……、wn，每两个整数之间用一个空格隔开，wi表示 i 号同学的接水量。
    1 ≤ n ≤ 10000，1 ≤ m ≤ 100 且 m ≤ n；
    1 ≤ wi ≤ 100。
输出
    输出只有一行，1 个整数，表示接水所需的总时间。
样例输入
    样例 #1：
    5 3
    4 4 1 2 1
    样例 #2：
    8 4
    23 71 87 32 70 93 80 76
样例输出
    样例 #1：
    4
    样例 #2：
    163

这题与上题的区别，是“排队是固定的，但是水龙头是按条件变动的”。所以是把每次增加一个后的龙头，排一次序。
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    int b;
    int a[1000];
    memset(a,0,sizeof(a));
    for(int i=0;i < n;i++)
    {
        cin>>b;
        a[0]=a[0]+b;
        sort(a,a+m);
    }
    cout<<a[m-1]<<endl;
    return 0;
}


3) P1223:*接水问題；
ss2339/1442是同題错解，结果是没排序前的错解，老师搞错测试点，许多同学“对”了
题目描述：
有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。
输入格式：
输入文件共两行，第一行为n；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。
输出格式：
输出文件有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。
输入样例#1：
10
56 12 1 99 1000 234 33 55 99 812
输出样例#1：
3 2 7 8 1 4 9 6 10 5
291.90
说明
n<=1000
ti<=1e6，不保证ti不重复
当ti重复时，按照输入顺序即可（sort是可以的）

题目分析：这一题的处理是例1的形态，稍微复杂化。题目需要输出，“最优化”时的状态，所以需要转为结构，记录下本来的ID，其他处理跟第一题相同。
#include "bits/stdc++.h"
using namespace std;
struct person
{
    int t;
    int idx;
} a[10000001];
bool comp(person a, person b){    return a.t < b.t;}
int main()
{
    double avr;
    double s = 0, t = 0;
    int n;
    cin >> n;
    for(int i=1; i<=n; i++)
    {
            cin >> a[i].t;
            a[i].idx = i;
    }
    sort(a+ 1, a+ (n+1), comp);
    for(int i=1; i<= n; i++)
    {
            cout << a[i].idx <<" ";
            t = t + a[i-1].t;
            s = s + t;
    }
    avr = s / n;
    printf("\n%.2f", avr);
}