贪心算法总结

MoonCake2011 · 2023-04-14 23:58:43 · 个人记录

贪心策略

贪心策略是一种可以比较快求解的方法

它一般配着排序使用

什么是贪心

贪心是以局部最优解顶替全局最优解

通常贪心需要证明

反证法

例题:P2240

此题我们很好想出 贪心 策略：

先取性价比 (x.v/v.m) 高的，再取性价比低的(局部最优)

证明：

如果你选了一个性价比低的，你可以用一个性价比高的等效代替

这种证明叫反证法

代码:

#include<bits/stdc++.h>
using namespace std;
struct coin{
    int m,v;
}a[110];
bool operator < (coin x,coin y){
    return x.v*y.m<y.v*x.m;
} 
bool operator > (coin x,coin y){
    return x.v*y.m>y.v*x.m;
} 
void quicksort(int l,int r){
    int i=l,j=r;
    coin flag=a[l+r>>1];
    do{
        while(a[i]>flag) i++;
        while(a[j]<flag) j--;
        if(i<=j) swap(a[i++],a[j--]);
    }while(i<=j);
    if(l<j) quicksort(l,j);
    if(i<r) quicksort(i,r);
}
int n;
int t,l;
double ans;
int main() {
    cin>>n>>t;
    for(int i=1;i<=n;i++)
        cin>>a[i].m>>a[i].v;
    quicksort(1,n);
    for(int i=1;i<=n;i++)
        if(l+a[i].m<t)
            ans+=a[i].v,l+=a[i].m;
        else{
            ans+=(t-l)*1.0/a[i].m*a[i].v;//装剩余空间
            break;
        }
    printf("%.2lf",ans);
   return 0;
}

那么，如果这是不可分割的金块呢，还能用贪心吗?

当然不能，因为这会出现这种情况

O

O A

O A

P A

P A

P A

我们发现 A 柱比 O 与 P 柱加起来要少，这时又不能装其他东西了，

选A柱（大的）比 选 O , P 柱要坏

这就是错误的贪心

为什么这题可以用贪心呢？

因为这题是装满背包，所以装一个不会影响下一个要不要装

也不会出现O P 柱超 A 柱的情况（直接补全）

可以用贪心算法

所以贪心算法只适用于无后效性的题

数学归纳法

例题:P1080

假设只有两个大臣，为 1号 与 2号

手上两个数分别是 (a1,a1) , (a2,b2) .

国王手上两数是 (a0,b0)

假设 把 1号 排 2号 前面最优

列出不等式:

同除 a0

因为 0<a,b<10000

所以 1/b1≤1≤a1/b2,1/b2≤1≤a2/b1

推出 a1/b2≤a2/b1

因为0<b1,b2

根据 不等式两边同乘同一个正数，不等号方向不变

推出 a1*b1<=a2*b2

所以按 a*b 排序就可达最优解

再看数据范围:

答案超了 10^{30000}

需要用高精度(封装)

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
    int a,b;
}a[1010],t;
bool operator < (node x,node y){
    return x.a*x.b<y.a*y.b;
}
bool operator > (node x,node y){
    return x.a*x.b>y.a*y.b;
}
void quicksort(node a[],int l,int r){
    int i=l,j=r;
    node flag=a[l+r>>1];
    do{
        while(a[i]<flag) i++;
        while(a[j]>flag) j--;
        if(i<=j) swap(a[i++],a[j--]);
    }while(i<=j);
    if(l<j) quicksort(a,l,j);
    if(i<r) quicksort(a,i,r);
}
struct LL{
    int a[30010];
    int len;
    LL(int x=0){
        memset(a,0,sizeof a);
        len=0;
        while(x)
            a[++len]=x%10,x/=10;
    }
    int &operator [] (int i){
        return a[i];
    }
    void fl(int l){
        len=l;
        for(int i=1;i<=len;i++) 
            a[i+1]+=a[i]/10,a[i]%=10;
        while(!a[len] && len>0) len--;
    }
    void print(){
        for(int i=max(1,len);i>=1;i--) cout<<a[i];
        cout<<"\n";
    }
};
LL operator / (LL x,int y){
    int len=x.len;
    LL c;
    for(int i=len;i>=1;i--)
        c[i]+=x[i]/y,x[i-1]+=x[i]%y*10;
    c.fl(len);
    return c;
}
LL operator * (LL x,int y){
    LL c;
    for(int i=1;i<=x.len;i++)
        c[i]=x[i]*y;
    c.fl(x.len+20);
    return c;
}
bool operator < (LL x,LL y){
    if(x.len!=y.len) return x.len<y.len;
    int len=max(x.len,y.len);
    for(int i=len;i>=1;i--)
        if(x[i]!=y[i])
            return x.len<y.len;
    return false;
}
LL ans;
int main() {
    cin>>n;
    cin>>t.a>>t.b;
    for(int i=1;i<=n;i++)
        cin>>a[i].a>>a[i].b;
    quicksort(a,1,n);
    LL sum=LL(t.a);
    for(int i=1;i<=n;i++){
        LL mon=sum/a[i].b;
        ans=max(mon,ans),sum=sum*a[i].a;
    }
    ans.print();
    return 0;
}

这种推理方法很妙是吧

这种方法叫数学归纳法

也就是用数学公式推贪心策略

一般用来证明排序

线段覆盖类型

例题:P1803

这道题乍一看挺简单

上 dfs

在一看

笑容逐渐消失

考虑贪心策略

我从局部最优开始考虑

局部最优是 你参加比赛结束最早(就有更多时间去参加更多比赛)

考虑后效性

选择此比赛并没有阻止前面比赛的选择

所以没有后效性

反证

如果选择此比赛，影响了同一时间的比赛的选择

(贪心策略以保证此比赛结束时间比同一时间的比赛结束时间早)

情况1:

__AAAAAA____CCCCCCC

你不论选 A 或选 B 都可以搞两场

此时可以以 A 统计.

情况2:

这时，选 A 比选 B 可以多选一个 C.

其实比赛相交只有这两种情况(利用无后效性将区间分块)

于是贪心成立

但是还要考虑一种情况：时间冲突

那我们的策略是能放就放,这样可以让参加更多比赛

代码:

#include<bits/stdc++.h>
using namespace std;
struct node{
    int b,e;
}a[int(1e6)+10];
bool operator < (node x,node y){
    return x.e<y.e;
}
bool operator > (node x,node y){
    return x.e>y.e;
}
void quicksort(int l,int r){
    int i=l,j=r;
    node flag=a[l+r>>1];
    do{
        while(a[i]<flag) i++;
        while(a[j]>flag) j--;
        if(i<=j) swap(a[i++],a[j--]);
    }while(i<=j);
    if(l<j) quicksort(l,j);
    if(i<r) quicksort(i,r);
}
int n,ans;
int main() {
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].b>>a[i].e;
    quicksort(1,n);
    int nxt=-2e9;
    for(int i=1;i<=n;i++)
        if(a[i].b>=nxt)
            ans++,nxt=a[i].e;
    cout<<ans;
    return 0;
}

我们可以用多角度的证明方法来证明复杂的贪心策略

一般顺序是 想贪心策略 -> 考虑后效性 -> (反证 或 数学归纳法)

还有，能放就放是一个很好的策略，只用考虑后效性

这种策略的题目有：

P4447

结尾

贪心策略是一种 可能翻车 也可能助你一臂之力的算法

但很多贪心题都很难，贪心思路很难想清

所以贪心难题基本是用 数学归纳法

记得，贪心一定要带上证明