贪心介绍

定义:在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解

我们先从一道例题感受贪心:

我们有n*m的矩阵
5 6 5 7 8 9 10
1 2 3 6 5 4 7 
2 3 6 5 4 7 8
1 6 4 8 7 4 6
1 3 6 5 4 7 4
每行选一个数,使总和最大,问怎么取?

很显然,每行取最大的就完了
10+7+8+8+7

这就是一个简单的贪心策略

贪心虽然好写,但是不好想,也不好证明,有时想错贪心策略还会爆零

那么我们要什么时候用贪心呢?

保证这个问题的子问题的最优解组合起来可以组成整个问题的整体最优解

比如以下这个题就不支持贪心了

5   4  0 0
-1 -1 -1 0
6   0 -1 0
4   5  2 0
从(1,1)走到(n,n),每次只能向下走或向右走

如果我们按照贪心思路走:5->4->0->0->0->0->0

但是最优解显然是5->-1->6->4->5->2->0

为什么呢？

因为子问题最优解不在无法组成整体最优解

模板

但是考场上直接想出贪心并证明其正确性就很难了,好在大多贪心都有模板

1.给出若干个区间，选出最多的区间个数使得区间两两不交

#include<bits/stdc++.h>
using namespace std;
struct Jack{
    int x,y;
}f[1101];
int n;
inline bool Jack(const Jack &a,const Jack &b){
    return a.y<b.y;
}
int main( ){
    std::ios::sync_with_stdio(false);
    cin>>n;
    int i,j,k=0,a,last;
    for(i=1;i<=n;i++)cin>>f[i].x>>f[i].y;
    sort(f+1,f+n+1,Jack);
    k++;
    last=f[1].y;
    for(i=2;i<=n;i++)
    if(f[i].x>=last){
        k++;
        last=f[i].y;
    }
    cout<<k<<endl;
}
思路:将区间按右端点排序,那么如果这个活动与以前的活动不冲突,就选择

2.给出若干个区间，选出最少的区间覆盖序列

#include<bits/stdc++.h>
using namespace std;
struct Jack{
    double x,y;
}f[15100];
double w,l;
int n;
inline bool Jackey(const Jack &a,const Jack &b){
    return a.x<b.x;
}
inline void work( ){
    cin>>n>>l>>w;
    double a,b;
    int i,j,k,cnt=0;
    double t;
    for(i=1;i<=n;i++){
        cin>>a>>b;
        if(b<=w/2)continue;
        cnt++;
        f[cnt].x=a-sqrt(b*b-w*w/4);
        f[cnt].y=a+sqrt(b*b-w*w/4);
    }
    sort(f+1,f+cnt+1,Jackey);
    i=1;
    t=0;
    int ans=0;
    while(t<l){
        ans++;
        int s=t;
        for(;i<=cnt&&f[i].x<=s;i++)
        t=max(t,f[i].y);
        if(t==s){
            cout<<-1<<endl;
            return;
        }
    }
    cout<<ans<<endl;
}
int main( ){
    std::ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)work( );
}
思路:我们可以通过简单的数学公式将每个水龙头能覆盖的区间求出来,就转化为了区间覆盖问题
那么区间覆盖问题怎么做呢？
我们首先根据左端点排序,如果当前区间有价值
重复进行:
枚举区间,选取 左端点在已选择范围内  右端点最大 的区间

3.选取最少的点覆盖所有区间

#include<bits/stdc++.h>
using namespace std;
bool vis[30100];
int m,n,ans=0;
struct Jack{int want,x,y;}f[6000];
inline bool Jackey(const Jack &a,const Jack &b){return a.y<b.y;}
int main( ){
    std::ios::sync_with_stdio(false);
    cin>>m>>n;
    int i,j,k;
    for(i=1;i<=n;i++)cin>>f[i].x>>f[i].y>>f[i].want;
    sort(f+1,f+n+1,Jackey);
    for(i=1;i<=n;i++){
        k=0;
        for(j=f[i].x;j<=f[i].y;j++)k+=vis[j];
        if(k>=f[i].want)continue;
        for(j=f[i].y;k<f[i].want;j--)
        if(!vis[j]){
            vis[j]++;
            ans++;
            k++;
        }
    }
    cout<<ans<<endl;
}
思路:
将区间按右端点排序
枚举区间,从右端点开始种树,直到区间内包含足够多的树木

4.加工调度问题

#include<bits/stdc++.h>
using namespace std;
int n;
struct Jack{
    int a,b,id;
}f[1100];
inline bool Jackey(const Jack &a,const Jack &b){
    return min(a.a,b.b)>min(b.a,a.b);
}
int main( ){
    std::ios::sync_with_stdio(false);
    cin>>n;
    int i,j,k;
    for(i=1;i<=n;i++)cin>>f[i].a,f[i].id=i;
    for(i=1;i<=n;i++)cin>>f[i].b;
    sort(f+1,f+n+1,Jackey);
    long long ans=f[1].a+f[1].b;
    for(i=2;i<=n;i++)ans+=f[i].a+f[i].b-f[i-1].b;
    cout<<ans<<endl;
    for(i=1;i<n;i++)cout<<f[i].id<<" ";
    cout<<f[n].id;
}

根据我做贪心的经验,这类问题我们可以考以下步骤AC(少数情况只能拿部分分)

我们假设加工序列先加工S1，再加工S2(假设的个数视题目需要而定)最优

则一定满足T(S1,S2)<T(S2,S1) (T指加工时间)

那么我们根据题意扩展出T(S1,S2),T(S2,S1)

再代回不等式列不等式方程

求得的关系即为加工序列需要满足的关系

在排序就求出加工序列

在此题中得出的关系既是

min(a.a,b.b)>min(b.a,a.b) (a先加工)

注:这种方法很玄学,对于大多数题是可行的,但是一部分题就不适用了,但也能拿可观的分

5.杂七杂八的贪心

#include<bits/stdc++.h>
using namespace std;
bool vis[31000];
int main( ){
    std::ios::sync_with_stdio(false);
    int m,n,i,j,k;
    cin>>m>>n;
    int a[31000],ans=0;
    for(i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    for(i=n;i>=1;i--)
    if(!vis[i]){
        for(j=i-1;j>=1;j--)
        if(!vis[j]&&a[i]+a[j]<=m){vis[j]=1;break;}
        ans++;
    }
    cout<<ans;
}
思路:很容易想到,将价值最大的和最小的分在一组即可

这种贪心就很恶心了,能不能做出来看人品,想出来就做出来，想不到就没了的那种

最后说一句

首先判断是否可以是用贪心:

1.贪心大多用来解决最值问题,一般数据范围N=1e7左右,不是线性dp就是贪心

2.看最优子结构是不是可以推出最优结构

贪心运用方面:

1.贪心优化:贪心不仅仅可以用来AC一道题,也可以用来优化代码,当时间复杂度及其庞大时,不妨常识用贪心之内的算法优化代码

2.贪心题:这种题就是裸的贪心了