【贪心】常见的几种贪心思路

贪心思路是解决很多思维题的利器。然而这种题没有固定模板，纯看赛时脑子零不灵活。能否快速切出思维题往往是取胜的关键。本文将收录一些常用的解题思路，持续更新中。

直接排序法

这种题一般排个序，按照要求每步选择最优解就可以。

P1803 线段覆盖

因为要参加更多的比赛，所以要优先选择结束更早的比赛，才能为后来的比赛创造更多的时间。直接按结束时间排序即可。

bool cmp(const pii&a,const pii&b)
{
    return a.second<b.second;
}
void solve()
{
    int n;
    cin>>n;
    vecpi a(n);
    mpi h;
    int idx=1;
    for(auto&p:a)
    {
        cin>>p.first>>p.second;
    }
    sort(a.begin(),a.end(),cmp);
    int ans=1;
    int cur=a[0].second;
    for(int i=1;i<n;i++)
    {
        if(a[i].first>=cur)
        {
            ans++;
            cur=a[i].second;
        }
    }
    cout<<ans<<endl;
}

CF810B Summer sell-off

显然把翻倍的机会给翻倍后对答案贡献更大的一组。定义cmp函数，将翻倍后对答案贡献大的排在最前面。

bool cmp(const pii&a,const pii&b)
{
    return min(2*a.first,a.second)-min(a.first,a.second)>min(2*b.first,b.second)-min(b.first,b.second);
}
void solve()
{
    int n,f;
    cin>>n>>f;
    vecpi a(n);
    for(auto&p:a)cin>>p.first>>p.second;
    sort(a.begin(),a.end(),cmp);
    int ans=0;
    for(int i=0;i<f;i++)
    {
        ans+=min(2*a[i].first,a[i].second);
    }
    for(int i=f;i<n;i++)ans+=min(a[i].first,a[i].second);
    cout<<ans<<endl;
}

调整相邻元素顺序不影响前面和后面的问题

NOIP2012 国王游戏

选取任意的i，j两个大臣，调整这两位的顺序对后面的问题不产生影响，我们只要使得这两位大臣中获得较多奖赏的那位获得的奖赏尽量少即可。

设i之前大臣的乘积为k，答案为max(k/bi, k·ai/bj)。因此定义比较函数对a*b的乘积进行排序。

# VLSMB_PythonProjectACM
class node:
    def __init__(self, a, b):
        self.x = a
        self.y = b
    def __lt__(self, other):
        return self.x * self.y < other.x * other.y
    def __str__(self):
        return f"{self.x} {self.y}"

if __name__ == "__main__":
    n=int(input())
    a,b=map(int, input().split())
    l=[]
    for i in range(n):
        x,y=map(int,input().split())
        l.append(node(x,y))
    l=sorted(l)
    ans=0
    cur=a
    for i in l:
        ans=max(ans,cur//i.y)
        cur*=i.x
    print(ans)

加工生产调度

P1248 加工生产调度

需要让AB的等待时间之和最短。A优先加工时间短的任务，而B优先加工时间长的任务。

两者综合考虑，优先排min(a,b)小的元素，如果min(a,b)==a则排前面，反之排后面。

最后模拟这个过程计算所需时间。

struct node
{
    int a,b,i;
    node():a(0),b(0),i(0) {}
    node(const node&x):a(x.a),b(x.b),i(x.i) {}
};
bool cmp(const node&x,const node&y)
{
    return min(x.a,x.b)<min(y.a,y.b);
}
void solve()
{
    int n;
    cin>>n;
    vector<node> a(n);
    for(int i=0;i<n;i++)cin>>a[i].a,a[i].i=i+1;
    for(int i=0;i<n;i++)cin>>a[i].b;
    vector<node> b(a);
    sort(b.begin(),b.end(),cmp);
    int i=0,j=n-1;
    for(int k=0;k<n;k++)
    {
        if(min(b[k].a,b[k].b)==b[k].a)a[i++]=b[k];
        else a[j--]=b[k];
    }
    int ans=0,sum=0;
    for(int i=0;i<n;i++)
    {
        sum+=a[i].a;
        ans=max(ans,sum);
        ans+=a[i].b;
    }
    cout<<ans<<endl;
    for(int i=0;i<n;i++)cout<<a[i].i<<' ';
    cout<<endl;
}

按位拆分

比较常见的就是求异或运算的最优解。因为异或运算每一位是独立的，所以可以每一位单独考虑，最后合并答案。

「CodePlus 2017 11 月赛」可做题

const int N = 1e5+5;
int dp[N][31],len[N];

void solve()
{
    int n,m;
    cin>>n>>m;
    vecpi a(m+1);
    for(int i=1;i<=m;i++)cin>>a[i].first>>a[i].second;
    sort(next(a.begin()),a.end());
    int cur=0,pos=1;
    for(int i=1;i<=m;i++)
    {
        // 连续已知区间的后面要填这个区间的异或和，此时b为0
        if(i!=1&&a[i].first!=a[i-1].first+1)
        {
            pos++;
            cur=0;
        }
        cur^=a[i].second;
        // 记录连续区间每一bit的1的个数
        for(int j=0;j<=30;j++)dp[pos][j]+=((cur>>j)&1);
        len[pos]++;
    }
    int ans=0;
    for(int i=1;i<=pos;i++)
    {
        if(a[i].first==1)for(int j=0;j<=30;j++)ans+=(dp[i][j]<<j);
        else for(int j=0;j<=30;j++)ans+=min(dp[i][j],len[i]-dp[i][j]+1)<<j;
    }
    cout<<ans<<endl;
}

优先队列与反悔贪心

POI2012 HUR-Warehouse Store

最初的思路是能卖则卖，然而这种思路是短浅的。有可能第一天卖出较大量的货物，导致无法满足后几天需求小的订单。

用一个优先队列维护之前买家的购买数量，当无法满足当前订单时，与先前的最大值进行比较，如果小于之前的最大值则舍弃之前买家的订单。

struct node
{
    int b,i;
    node():b(0),i(0) {}
    node(const node&x):b(x.b),i(x.i) {}
};
bool operator<(const node&x,const node&y)
{
    return x.b<y.b;
}
void solve()
{
    int n;
    cin>>n;
    veci a(n+1);
    veci vis(n+1);
    vector<node> b(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i].b,b[i].i=i;
    priority_queue<node> q;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        sum+=a[i];
        if(sum>=b[i].b)
        {
            sum-=b[i].b;
            vis[i]=1;
            q.push(b[i]);
        }
        else if(!q.empty()&&q.top().b>b[i].b)
        {
            vis[q.top().i]=0;
            sum+=q.top().b;
            q.pop();
            sum-=b[i].b;
            vis[i]=1;
            q.push(b[i]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)if(vis[i])ans++;
    cout<<ans<<endl;
    for(int i=1;i<=n;i++)if(vis[i])cout<<i<<' ';
    cout<<endl;
}

不记录满足天数的版本可能阅读性更好一些：

void solve()
{
    int n;
    cin>>n;
    veci a(n),b(n);
    for(auto&x:a)cin>>x;
    for(auto&x:b)cin>>x;
    int sum=0;
    priqli q;
    for(int i=0;i<n;i++)
    {
        sum+=a[i];
        if(sum>=b[i])
        {
            sum-=b[i];
            q.push(b[i]);
        }
        else if(!q.empty()&&q.top()>b[i])
        {
            sum+=q.top();
            q.pop();
            sum-=b[i];
            q.push(b[i]);
        }
    }
    cout<<q.size()<<endl;
}

逆向思维

CF506C Mr. Kitayuta vs. Bamboos

对于最值最化这种问题，通常使用二分法去找符合条件的答案。

同时这题正向编码判断比较困难，可以反过来判断，则假设每个竹子都从H长度开始，看推回到第一天时是否满足题意。

veci h,a;
bool check(int H,int n,int m,int k,int p)
{
    priqgpi q;
    for(int i=1;i<=n;i++)
    {
        if(h[i]+m*a[i]<=H)continue;
        q.push({H/a[i],i});
    }
    veci ht(n+1);
    for(int i=1;i<=n;i++)ht[i]=H;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=k;j++)
        {
            if(q.empty())return true;
            pii t=q.top();
            q.pop();
            if(t.first<i)return false;
            ht[t.second]+=p;
            t.first=ht[t.second]/a[t.second];
            if(ht[t.second]-m*a[t.second]<h[t.second])q.push(t);
        }
    }
    return q.empty();
}
void solve()
{
    // 对于最大值最小化、最小值最大化这种问题，使用二分法确定答案
    // 判断答案是否合理
    int n,m,k,p;
    cin>>n>>m>>k>>p;
    h.resize(n+1);
    a.resize(n+1);
    for(int i=1;i<=n;i++)cin>>h[i]>>a[i];
    int l=0,r=0;
    for(int i=1;i<=n;i++)r=max(r,h[i]+a[i]*m),l=max(l,a[i]);
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(mid,n,m,k,p))r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
}