贪心算法

    根据贪心算法的定义：贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。        

    初学者看到这个定义就很懵，看完感觉跟没看一样，觉得这就是在说废话。这个初学者就是我，刚开始想刷贪心的题目练练手的，想着先学习一下他的具体用法，结果发现贪心根本就没有套路，需要不断刷题来培养贪心思路。        

下面给出我做的第一个贪心题目：

    在一个月黑风高的暴风雨夜，Farmer John 的牛棚的屋顶、门被吹飞了 好在许多牛正在度假，所以牛棚没有住满。 牛棚一个紧挨着另一个被排成一行，牛就住在里面过夜。有些牛棚里有牛，有些没有。 所有的牛棚有相同的宽度。 自门遗失以后，Farmer John 必须尽快在牛棚之前竖立起新的木板。他的新木材供应商将会供应他任何他想要的长度，但是吝啬的供应商只能提供有限数目的木板。 Farmer John 想将他购买的木板总长度减到最少。 给出 m,s,cm,s,c，表示木板最大的数目、牛棚的总数、牛的总数；以及每头牛所在牛棚的编号，请算出拦住所有有牛的牛棚所需木板的最小总长度。

    刚开始做时，不知道贪心是什么个操作，就纯用代码模拟题目，最愚蠢的是刚开始我用定义了一个牛棚总数大小的数组来模拟牛棚，赋初值为0代表没有牛，后面根据输入的信息将有牛的牛棚赋值为1，然后从头到尾遍历牛棚数组，遇到一个有牛的牛棚后计算它和上一个牛棚的距离和下一个牛棚的距离，如果距离上个牛棚近它们就用一块板子，否则将它和下一个牛棚绑定在一起，木板数量+1，同时计算木板的长度；        

    通过这样的思路很快写出了代码，测试样例输入一下，对了！但是提交WR，经过样例分析才发现存在很多bug。改了很久也没有想到正确的思路，于是去了神秘的题解区......        

     通过借鉴学习，我才明白这题贪心的要义，根本不需要定义数组模拟牛棚，我们只需要知道每个相邻的牛棚之间的距离，首先假设只有一个木板从第一只牛一直连到最后一只牛，然后根据木板数量优先选择距离最长的距离给他砍掉，这就是这题贪心的地方，每次都选择距离最长的无用木板给它砍掉，通过不断的砍掉最大间距木板，多用一个木板，节省木板的长度，一个个的局部最优结果迭代成最终的最优结果。         其中有特殊情况，比如木板数量大于牛的数量，那么直接返回牛的个数就可以了，不需要在进行排序等等操作了。

#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int m,s,c,length=0;
    cin>>m>>s>>c;
    if(m>c)
    {
        cout<<c;
        return 0;
    }
    int np[c],gap[c+1];
    for(int i=0;i<c;i++)
        cin>>np[i];
    sort(np,np+c);
    length=np[c-1]-np[0]+1;
    for(int i=1;i<c;i++)
        gap[i]=np[i]-np[i-1];
    sort(gap+1,gap+c,cmp);
    for(int i=1;i<m;i++)
        length-=gap[i]-1;
    cout<<length;
    return 0;
}