贪心

引言

贪婪是一种人类本能的东西，贪心算法也是最接此人类平常思维的一种解题策略。其实，在解决一些日常问题时，我们本能就怀着对目标最直观、 最简单、最高效的思路，其中往往就带有贪心思想的影子。虽然它不能保证求得的最后解一定是最佳的，但是它可以为某些问题确定一个可行性范围。在某些范围内，贪心算法是我们的最佳选择。

贪心法的基本思想

贪心法是从问题的某个初始解出发，采用逐步构造最优解的方法，向给定的目标前进。在每一个局部阶段，都做一个在当前“看上去”最优的决策，并期望通过每一次所做的局部最优选择产生出一个全局最优解。做出贪心决策的依据称为“贪心策略”。要注意的是，贪心策略一旦做出，就不可再更改。

与搜索、动态规划不同的是，贪心只是一种策略或方法，而不是算法。推进的每一步不是依据某一个固定的递推式，而是做一个当时“看似最佳”的贪心选择（操作），不断将问题归纳为更小的相似子问题。所以，归纳、分析、选择正确合适的贪心策略，是解决贪心问题的关键。

贪心算法的步骤

$\color{blue}{【真正意义要求解原问题】}$

从问题的某一初始解出发

$\color{blue}{【将原问题变成更小子问题的步骤】}$

$while$ 能朝给定总目标前进一步

$do$ 求出可行解的一个解元素

$\color{blue}{【整理解】}$

由所有解元素组合成问题的一个可行解

贪心法的正确性证明

对于一个问题，如果想用贪心法求解，首先要想到基于某种“序”或者“规则”的贪心策略。

其次还要能证明其正确性。 要严格证明一个贪心算法的正确性是很困难的，目前最有效的一种方法叫“矩阵胚理论”，但是很复杂。信息学竞赛中常用的贪心证明方法，一般有反证法、构造法、调整法。其实，即使一个贪心算法是不完全正确的，也可以努力寻找一些调整方法，或 制定多种贪心策略，通过调整优化、比较择优来争取得到最优解 ，甚至也可以先得到一个“较优”解，然后，在此基础上进行搜索剪枝或分支定界。

构造法

根据描述的算法，用贪心的策略依次构造出一个解，可证明一定是合法的解。即用贪心法找可行解。

反证法

用贪心的策略，依次构造出一个解 $S1$ ，假设最优解 $S2$ 不同于 $S1$ ，可以证明是矛盾的，从而得出 $S1$ 就是最优解。

调整法

用贪心的策略，依次构造出一个解 $S1$ 。假设最优解 $S2$ 不同于 $S1$ ，找出不同之处，在不破坏最优性的前提下，逐步调整 $S2$ ，最终使其变为 $S1$ ，从而 $S1$ 也是最优解。

题目

A：修理牛棚

这题可以使用调整法。

考虑如何使总长度最短。因为有些位置没有牛，所以有些牛棚是不需要覆盖木板的。如果能每个牛棚分单独一个木板，一定总长度是最小的。但是由于木板数量有限制，所以我们有时只能用一个比较长的木板的时候，顺便把没有牛的牛棚也覆盖了。就造成了浪费。所以一定是使用最大数目木板的。

第一头牛的位置在 $a_1$ ，最后一头牛的位置在 $a_c$ 。先考虑把整个木板覆盖在 $[1,c]$ ，这显然是最不优的选择。题目要求最多只能使用 $M$ 块木板，我们可以把它转化为木板只能有 $M-1$ 个空隙。也就是说我们可以先覆盖整个区间，再选择 $M-1$ 处空隙去掉。根据贪心可以得出，去掉最长的 $M-1$ 个空隙可以使总长度尽量短。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1100;
int m,c,a[N],b[N],sum;
bool cmp(int a1,int a2)
{
    return a1>a2;
}
int main()
{
    scanf("%d%d",&m,&c);
    if(m>=c)//特判 
    {
        printf("%d",c);//如果可以使用的木板数够用，可以一个牛棚用一块木板 
        return 0;
    }
    for(int i=1;i<=c;i++) scanf("%d",&a[i]);
    sort(a+1,a+c+1);
    for(int i=1;i<c;i++) b[i]=a[i+1]-a[i]-1;//算出每个空隙的长度 
    sort(b+1,b+c,cmp);//把空隙长度从小到大排序 
    for(int i=1;i<m;i++) sum+=b[i];//选择最长的M-1个空隙 
    printf("%d",a[c]-a[1]+1-sum);
    return 0;
}

B：删数问题

这题可以使用构造法

如果采取“找最大的数字删除”这种贪心思想，答案显然是错误的。比如 $13542972$ ，答案为 $13297$ ，而不是 $13542$ 。

为了使数字变大，某个数字删去后一定要比原来大，于是我们得出贪心策略：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字；否则，删除第一个递减区间的首字符，这样删一位便形成了一个新数字串。然后回到数字串首，按上述规则再删下一个数字。重复以上过程 $s$ 次为止，剩下的数字串便是问题的解。

这样， 问题就转化为“求一个数字串的递减区间首字符” 。

还有 两个细节问题 ：

• 删除后会有前导 $0$ 的情况，要特判一下。

• 如果整个序列是升序的但是还没删完，就从后面删起。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=310;
string s;
int n,a[N],m,lastp;
bool r;
//因为某些数会被删除，所以导致i-1不一定是i的上一个数，可以用-1标记删除的数，使用循环从i-1开始往前遍历，找出第一个不等于-1的数 
int last(int p)//返回上一个（未被删除的）数 
{
    for(int i=p-1;i>=1;i--) 
    {
        if(a[i]!=-1) return i;
    }
    return 0;
}
int main()
{
    cin>>s>>m;
    for(int i=0;i<s.size();i++) a[i+1]=s[i]-'0';//将字符串转化为数字 
    n=s.size();
    for(int i=2;i<=n;i++)
    {
        lastp=last(i);//得到上一个数 
        if(lastp&&a[lastp]>a[i]) 
        {
            a[lastp]=-1;//删除，标记为-1 
            m--;
            i--;
        }
        if(!m) break;
    }
    for(int i=n;i>=1;i--)//如果整个序列是升序的但是还没删完，就从后面删起。
    {
        if(!m) break;
        if(a[i]!=-1)
        {
            a[i]=-1;
            m--;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]>0) r=true;//特判前导0 
        if(r&&a[i]!=-1) printf("%d",a[i]);
    }
    return 0;
}

C：蜈蚣

这题要运用 最不利原则 （就是要尽量取多）

贪心过程：

• 要穿的 $C \times F$ 只袜子都要取。（注意同一个颜色的袜子可以给多只蜈蚣穿，所以取第 $i$ 种颜色的袜子应该是 $a_i \div F$ ）

• 根据最不利原则，让蜈蚣凑不齐 $F$ 只颜色相同的袜子，所以小于 $F$ 的袜子也要取。

• 判断 $-1$ （袜子不够穿）

• 如果取了 $F-1$ 只后还能满足，则取 $(cnt-1)(F-1)$ 个（ $cnt$ 是 $\ge F$ 的颜色种类个数）

• 如果取了 $F-1$ 只后不能满足，更新数组 $a$ （ $a_i=a_i-(a_i-(F-1)) \div F \times F$ ），接着有 $cnt-c$ 只蜈蚣还没满足，所以还能取 $(cnt-c) \times (F-1)$ 只，最后再取 $a_i-F$

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=110;
int c,f,n,a[N],cnt,sum,num;
int main()
{
    scanf("%d%d%d",&c,&f,&n);
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&a[i]);
        cnt+=a[i]/f;
        if(a[i]<f) sum+=a[i];
    }
    if(cnt<c) 
    {
        printf("-1");
        return 0; 
    }
    sum+=c*f;//把要穿的取了 
    cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>=f) cnt++;
        num+=(a[i]-(f-1))/f;
    }
    if(num>=c) sum+=(cnt-1)*(f-1);//取了f-1只后还能满足 
    else//取了f-1只后不能满足 
    {
        c-=num;
        for(int i=1;i<=n;i++) a[i]-=(a[i]-(f-1))/f*f;//更新数组a 
        sort(a+1,a+n+1);
        sum+=(cnt-c)*(f-1);//有cnt-c只还没满足 
        for(int i=n,j=1;j<c;i--,j++) sum+=a[i]-f;
    }
    printf("%d",sum);
    return 0;
}

D：安装饮水机

这题是一道区间贪心。

我们既然要满足安装的饮水机最少，又要满足每个人都要喝到水。我们可以先求出 $l$ 和 $r$ 来表示每个人可以走到的最左和最右端点。这两个端点连成的线段就是每个人可以走到的区间。如果两个区间有重复，那么 $r$ 较小的那个区间如果将饮水机定在较后的位置，可以使得后面的区间可以走到这个饮水机的位置。根据贪心的思想，我们得出当饮水机定在 $r$ 的位置时，对后面的影响最大。

于是得出贪心策略：求出区间左右端点 $l$ 和 $r$ ，把区间按 $r$ 的大小排序。接着遍历 $[l,r]$ 这整个区间，如果区间内没有饮水机，就在 $r$ 的位置上建立一个饮水机。

证明：

每一个区间都一定包含一个点，所以当前选择方案是一种合法方案。假设最终答案是 $ans$ ，当前答案是 $cnt$ 。由于最优解是当前所有合法方案的最小值，所以 $ans \le cnt$ 。而找到 $cnt$ 个点就相当于找到 $cnt$ 个两两无交集的区间。要想覆盖所有区间，就至少需要 $cnt$ 个点，所以 $ans \ge cnt$。

$\because ans \le cnt,$ $ans \ge cnt$

$\therefore$ 得证 $ans=cnt$

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1100,M=150100;
int n,s,w,cnt;
struct node
{
    int l,r;
}a[N];
bool f,r[M]; 
bool cmp(node a1,node a2) 
{
    return a1.r<a2.r;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) 
    {
        scanf("%d%d",&s,&w);
        //算出每个人能走到的最左和最右位置 
        a[i].l=s-w;
        a[i].r=s+w;
        if(a[i].l<0) a[i].l=0;
    }
    sort(a+1,a+n+1,cmp);//按右端点大小排序 
    for(int i=1;i<=n;i++)
    {
        f=false;
        for(int j=a[i].l;j<=a[i].r;j++)//找区间内是否已经有饮水机 
        {
            if(r[j])
            {
                f=true;
                break;
            }
        }
        if(!f)//如果没有，则在r上建立一个 
        {
            r[a[i].r]=true;
            cnt++;
        }
    }
    printf("%d",cnt);
    return 0;
}