贪心小结

小 TAG

观察(贪心思路) 猜测(减少决策数量) 证明(从最优解转化为贪心解,并且不改变最优性质,从而证明)

多个贪心组合 贪心与非线性算法 贪心的单调性 贪心性质

贪心算法是一种形式及其多样的算法。它的应用方式很广,简单的简单,难的难。

贪心入门练习

CF949A Zebras

定义 Zebras 为这样的字串:0,010,01010,0101010…。给定一个 01 串,问能不能把这个 01 串拆成 zebras,要求每个 zebras 都是 01 串的subsequence。例如 001100=010,010

题目要求是子序列拆分,那么我们在构造 Zebra 的时侯,可以贪心地匹配最左边的 0 或 1。如果最后只剩下 1 就返回无解。

#include<bits/stdc++.h>
#define N 200011
using namespace std;

char s[N];
int s0[N],c0,s1[N],c1;
int nex[N],vis[N],k,l[N],st[N];

int main(){scanf("%s",s+1);
    for(int i=1;s[i];i++){
        if(s[i]=='0'){
            if(c1)nex[s1[c1]]=i,c1--;
            s0[++c0]=i;
        }
        else {
            if(c0)nex[s0[c0]]=i,c0--;
            else return printf("-1"),0;
            s1[++c1]=i;
        }
    }
    if(c1)return printf("-1"),0;
    for(int i=1;s[i];i++){
        if(!vis[i]){
            ++k;int len=0;
            for(int j=i;j;j=nex[j])vis[j]=true,len++;
            l[k]=len,st[k]=i;
        }
    }
    printf("%d\n",k);
    for(int i=1;i<=k;i++){
        printf("%d",l[i]);
        for(int j=st[i];j;j=nex[j])printf("%d",j);
        printf("\n");
    }
    return 0;
}

CF1003D Coins and Queries

有 n 个硬币,每个硬币的面值都是 2 的非负整数次幂,面值不超过

有 m 个询问,给定 q,询问可以凑成 q 的最小硬币数是多少。 .

贪心思路:从大到小减(大的一定是小的的倍数)。

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int n,q;
int coin[N];//coin[i]:the number of 2^i coin.
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1,a;i<=n;i++){
        scanf("%d",&a);
        int p=0;
        for(int i=1;i<=a;i<<=1,p++);--p;
        coin[p]++;
    }
    for(int i=1,a;i<=q;i++){
        scanf("%d",&a);
        int p=0,s=0,t;
        for(int i=1;i<=a;i<<=1,p++);--p;
        while(p>=0)t=a/(1<<p),t=min(t,coin[p]),s+=t,a-=t*(1<<p),p--;
        if(a!=0)printf("-1\n");
        else printf("%d\n",s);
    }
    return 0;
}

CF917A The Monster

一个包含 ( ) ? 的序列,? 可以变成 () 。我们认为一个合法的括号序列要求其括号是相互匹配的。例如 () (())() (? 。问一个序列的非空合法括号子串的个数。

对于每个字符 开头的子串 处理,贪心地把 ? 先当做 );如果 )( 多了再换成 ). 复杂度

#include<bits/stdc++.h>
using namespace std;
char s[5010];
int tot;
int main(){scanf("%s",s);
    for(int i=0;s[i];i++){//start
        int q=0,cur=0;
        for(int j=i;s[j];j++){if(s[j]=='(')cur++;
            else if(s[j]==')')cur--;
            else q++,cur--;// 把?当作)
            if(cur<0){if(q>0)q--,cur+=2;// 为负数,把?换成(
                else break;// 没有?可以换了,后面的都不是了
            }
            if(cur==0)tot++;
        }
    }
    printf("%d",tot);
    return 0;
}

CF909E Coprocessor

你有 N 个任务,每个任务要么只能在 Coprocessor 上处理,要么在 Main Processor 上处理。你的一些任务是有依赖关系的,一共 M 个关系。保证关系无环。一个任务能被执行当且仅当该任务的依赖任务都完成。

调用一次 Coprocessor,可以处理若干任务,但这个任务要么依赖任务都完成,要么依赖任务也在这次处理的任务集合中。对于在 Main Processor 上处理的任务,只要它的依赖任务都处理完了,它就会自动地处理这个任务。

问调用 Coprocessor 的最少次数。

依赖关系是个 DAG。哪些任务是不能同时被 Coprocessor 处理的?即在一条依赖路径上被一个 Main Processor 任务断开的任务。因为你必须先把这个 Main Processor 任务处理了再处理后面的 Coprocessor。于是我们就相当于求一个 DAG 上的所有路径中,Coprocessor 任务链的个数最大的路径。任务链的个数就是调用的次数。这个可以记忆化搜索做。

#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,m,ans;
int e[N],id[N],F[N],v[N];
vector <int> d[N];
int f(int k){// 要完成任务 k 的最少调用次数(路径上调用 co 组成的链的最大个数) 
    if(v[k])return F[k];
    else if(e[k]==1){F[k]=1;
        for(int i=0;i<d[k].size();i++){
            if(e[d[k][i]]==1)F[k]=max(F[k],f(d[k][i]));
            else F[k]=max(F[k],f(d[k][i])+1);
        }
    }
    else for(int i=0;i<d[k].size();i++)F[k]=max(F[k],f(d[k][i]));
    return v[k]=1,F[k];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)scanf("%d",&e[i]);
    for(int i=0,x,y;i<m;i++){
        scanf("%d%d",&x,&y);
        d[y].push_back(x),++id[x];
    }
    for(int i=0;i<n;i++)if(!id[i])ans=max(ans,f(i));
    printf("%d",ans);
    return 0;
}

CF767E Change free

你有 N 天和 M 个 1 元硬币和无数张 100 元钞票。每一天你的消费金额是 。你消费时可以找零,但找零会带来不满意度。第 i 天,找零的不满意度是 。问如何支付,不满意度最小。

先每次都用零钱支付,如果硬币数量变成了负数,就将之前用零钱支付的天中找到代价(dissatisfaction)最小的那天,让那一天用 100 元支付。

于是你的硬币数会增加 100 元,而代价相应增加。

用优先队列 or 堆维护。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100005;
ll n,m,tot;
ll c[N],w[N],v[N];

struct data{
    ll p,w;
    bool operator<(data tht)const{return w>tht.w;}
};
priority_queue <data> q;

int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(ll i=1;i<=n;i++)cin>>c[i],v[i]=c[i]/100,c[i]%=100;
    for(ll i=1;i<=n;i++)cin>>w[i],w[i]*=(100-c[i]);
    for(ll i=1;i<=n;i++){m-=c[i];
        if(c[i])q.push((data){i,w[i]});
        if(m<0){
            m+=100;
            tot+=q.top().w;
            v[q.top().p]++,c[q.top().p]=0;
            q.pop();
        }
    }
    cout<<tot<<endl;
    for(ll i=1;i<=n;i++)cout<<v[i]<<' '<<c[i]<<endl;
    return 0;
}

CF484A Bits

N 次,询问 区间中二进制表示下 1 的个数最多的数。如果有多个答案,输出最小的。

贪心,在 l 上从低位往高位补 1,直到超过 r 就输出。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,l,r;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>l>>r;
        for(ll cur=1;cur<=r;cur<<=1){
            if((l&cur)==0){
                if(l+cur>r)break;
                else l+=cur;
            }
        }
        printf("%lld\n",l);
    }
    return 0;
}

HNOI2003 消防局的设立

一个白色结点的边权为 1 的树,问最少染多少个黑色结点使得任意结点距离为 2 的范围内都有黑点。

不要相信洛谷的标签

一道典型的贪心

每次找深度最大的结点,在他的爷爷结点放一个消防站

使用 STL 优先队列 & 延迟删除法

#include<bits/stdc++.h>
using namespace std;
const int N=10000;
int n,r=1,ans;
struct node{int p,s,b,v;};
node t[N];
void add_son(int p,int s){t[s].p=p,t[s].b=t[p].s,t[p].s=s;}

struct data{
    int idx,dp;//index,deep
    bool operator<(data tht)const{return dp<tht.dp;}
};
priority_queue<data> q;
bool del[N];// 延迟删除

void dfs_push(int rt,int dp){
    q.push((data){rt,dp});
    for(int i=t[rt].s;i;i=t[i].b)dfs_push(i,dp+1);
}
void mark(int rt){
    for(int s=t[rt].s;s;s=t[s].b){
        del[s]=1;
        for(int ss=t[s].s;ss;ss=t[ss].b)del[ss]=1;
    }
    for(int s=t[t[rt].p].s;s;s=t[s].b)del[s]=1;
    del[t[rt].p]=del[t[t[rt].p].p]=1;
}
int main(){
    scanf("%d",&n);
    for(int i=2,x;i<=n;i++){
        scanf("%d",&x);
        add_son(x,i);
    }
    while(t[r].p)r=t[r].p;
    dfs_push(r,1);
    while(!q.empty()){
        data now=q.top();q.pop();
        if(del[now.idx])continue;
        if(t[t[now.idx].p].p)mark(t[t[now.idx].p].p);
        else if(t[now.idx].p)mark(t[now.idx].p);
        else mark(now.idx);
        ans++;
    }
    printf("%d",ans);
    return 0;
}

RXD 课件中的贪心

奶牛异或

静态区间最大异或和。

异或和可以转化为前缀和。于是变成求 的最大值。

两个数的最大异或,可以从高位到低位贪心。能变成 1 就变成 1。相当于在字典树上走。于是对 建字典树,然后在树上查询即可。然后把 插入到字典树,考虑下一位。

NOI2014 起床困难综合症

有 M 个形如 的二元组分别表示做按位与或异或的操作。初始值在 内,问最后变换的最大值。

仍然是从高到底考虑,这一位能否变成 1。把 0 和 1 的情况都走一遍:

  1. 两个都能取或者都不能取,那么取 0(因为要贪心地保证在 内)
  2. 如果只能取 1 而且不会大于 m 就取 1
  3. 取 0

NOI2014 随机数生成器

题面很恶心。最后的简化问题是,一个 的矩阵里填了 的排列,每次只能朝右 or 下走,问从左上到右下的路径中,权值排序后字典序最小的路径。

思路显然,先走 1。然后你发现你就只能走 1 的左上矩阵和右下矩阵。那么在这两个矩阵中找到第二小的值,一直这样缩小范围即可。可以倒序循环实现。


  转载请注明: Sshwy's Blog 贪心小结

 上一篇
单调队列小结 单调队列小结
单调队列故名思义,单调队列旨在维护一个队列,其中元素始终以某一关键字单调的顺序排列 单调队列的思想广泛用于最优解的维护,用于优化 1D/1D 动态规划 朝花中学 OI 队的奋斗历程——浅谈单调队列 [NOIP2016] 蚯蚓优先队列每次取最
2018.12.19
下一篇 
并查集 ·Disjoint 并查集 ·Disjoint
摘要 并查集(Union-Find Set)用于处理元素间可传递的关系,通常以集合的方式呈现。 并查集本身又是一种树结构(由若干棵树组成的不相交森林),用树的根结点(代表元)来区分不同的集合。 并查集并查集支持以下基本操作: Get(
2018.12.19
  目录