反悔贪心小结

Sky_Maths · 2023-10-06 20:41:09 · 个人记录

前言

题单Link
需要注意的是，这只是一类反悔贪心，博大精深的反悔贪心并不是能够以偏概全的，还需具体情况具体分析！！！

正文

首先我们要知道，反悔贪心其实属于模拟费用流的一种。
所以反悔贪心由两部分组成：寻找增广路（构造替换方案），流动 1 流量
具体而言，反悔贪心的套路，考虑构造几种替换方案（即不同种类的增广路），使得每次更进一步（即流量 +1 ），并且能够覆盖所有可能的情况。
反悔贪心的代码，首先需要堆和分类数组vis。
如果你不知道怎么为堆命名：建议用 q01 这种形式，代表从种类 0 变成种类 1

设共有 w 次增广

（增广前）每个堆都加入一个边界值，注意不同类别的堆用不同的值，别忘了修改分类数组
（w次增广）for i 1 to w
对于每种情况的堆判断堆顶是否满足是该种情况
判断最小费用的增广路是哪条
    case 情况1：...
    case 情况2：...
    case 情况3：...

或者

总结套路

建模
找增广路
将当前状态分类
根据状态将增广路具体为改变种类的操作

需要注意的是，这只是一类反悔贪心，博大精深的反悔贪心并不是能够以偏概全的，还需具体情况具体分析！！！

代码举例

主要对照上文的伪代码看代码格式

CF436E

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define rep(i,l,r) for(int i(l),i##end(r);i<=i##end;++i)
using namespace std;
typedef long long ll;
typedef pair<ll,int> pii;
const int N = 3e5 + 9;
const ll INF = 0x3f3f3f3f3f3fLL;
int n,w;
int a[N],b[N],vis[N];
ll val1,val2,val3,val4,ans;
priority_queue<pii,vector<pii>,greater<pii> > q01,q02,q12,q10,q21;
void In(int i) {
    if(vis[i]==0) q01.push(mp(a[i],i)),q02.push(mp(b[i],i));
    if(vis[i]==1) q12.push(mp(b[i]-a[i],i)),q10.push(mp(-a[i],i));
    if(vis[i]==2) q21.push(mp(a[i]-b[i],i));
}
main() {
    scanf("%d%d",&n,&w);
    rep(i,1,n) scanf("%d%d",&a[i],&b[i]);
    rep(i,1,n) In(i);
    vis[n+1]=0;
    vis[n+2]=1;
    vis[n+3]=2;
    q01.push(mp(INF,n+1)); q02.push(mp(INF,n+1));
    q10.push(mp(INF,n+2)); q12.push(mp(INF,n+2)); 
    q21.push(mp(INF,n+3)); 
    rep(i,1,w) {
        while(vis[q01.top().se]!=0) q01.pop();
        while(vis[q02.top().se]!=0) q02.pop();
        while(vis[q12.top().se]!=1) q12.pop();
        while(vis[q10.top().se]!=1) q10.pop();
        while(vis[q21.top().se]!=2) q21.pop();
        val1=q01.top().fi;
        val2=q12.top().fi;
        val3=q21.top().fi+q02.top().fi;
        val4=q10.top().fi+q02.top().fi;
        ll minn=min(min(val1,val2),min(val3,val4));
        ans+=minn;
        if(val1==minn) {
            vis[q01.top().se]=1; In(q01.top().se);
            continue;
        }
        if(val2==minn) {
            vis[q12.top().se]=2; In(q12.top().se);
            continue;
        }
        if(val3==minn) {
            vis[q21.top().se]=1; In(q21.top().se);
            vis[q02.top().se]=2; In(q02.top().se);
            continue;
        }
        if(val4==minn) {
            vis[q10.top().se]=0; In(q10.top().se);
            vis[q02.top().se]=2; In(q02.top().se);
            continue;
        }
    }
    printf("%lld\n",ans);
    rep(i,1,n) printf("%d",vis[i]);
    return 0;
}

Luogu P5470

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define rep(i,l,r) for(int i(l),i##end(r);i<=i##end;++i)
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
const int N = 2e5 + 9;
const ll INF = 0x3f3f3f3f3f3fLL;
int T,n,K,L,cnt;
int a[N],b[N],vis[N],oa[N],ob[N];//0 none,1 a,2 b,3 ab
ll ans,sum0,sum1,sum2,sum3,maxn;
priority_queue<pli> q03,q10,q13,q20,q23,q30;
bool cmpa(int u,int v) {return a[u]>a[v];}
bool cmpb(int u,int v) {return b[u]>b[v];}
void In(int i) {
    if(vis[i]==0) q03.push(mp(a[i]+b[i],i));
    if(vis[i]==1) q10.push(mp(-a[i],i)),q13.push(mp(b[i],i));
    if(vis[i]==2) q20.push(mp(-b[i],i)),q23.push(mp(a[i],i));
    if(vis[i]==3) q30.push(mp(-a[i]-b[i],i));
}
main() {
    // freopen("a.in","r",stdin);
    scanf("%d",&T);
    while(T--) {
        while(!q03.empty()) q03.pop();
        while(!q10.empty()) q10.pop();
        while(!q13.empty()) q13.pop();
        while(!q20.empty()) q20.pop();
        while(!q23.empty()) q23.pop();
        while(!q30.empty()) q30.pop();
        scanf("%d%d%d",&n,&K,&L);
        rep(i,1,n) scanf("%d",&a[i]);
        rep(i,1,n) scanf("%d",&b[i]);
        rep(i,1,n) oa[i]=i,ob[i]=i;
        sort(oa+1,oa+n+1,cmpa);
        sort(ob+1,ob+n+1,cmpb);
        rep(i,1,n) vis[i]=0;
        ans=0;
        rep(i,1,K) vis[oa[i]]|=1,ans+=a[oa[i]];
        rep(i,1,K) vis[ob[i]]|=2,ans+=b[ob[i]];
        vis[n+1]=0;
        vis[n+2]=1;
        vis[n+3]=2;
        vis[n+4]=3;
        q03.push(mp(-INF,n+1));
        q10.push(mp(-INF,n+2)),q13.push(mp(-INF,n+2));
        q20.push(mp(-INF,n+3)),q23.push(mp(-INF,n+3));
        q30.push(mp(-INF,n+4));
        rep(i,1,n) In(i);
        cnt=0;
        rep(i,1,n) if(vis[i]==3) ++cnt;
        rep(i,cnt+1,L) {
            while(vis[q03.top().se]!=0) q03.pop();
            while(vis[q10.top().se]!=1) q10.pop();
            while(vis[q13.top().se]!=1) q13.pop();
            while(vis[q20.top().se]!=2) q20.pop();
            while(vis[q23.top().se]!=2) q23.pop();
            while(vis[q30.top().se]!=3) q30.pop();
            sum0=q23.top().fi+q10.top().fi;
            sum1=q13.top().fi+q20.top().fi;
            sum2=q10.top().fi+q20.top().fi+q03.top().fi;
            sum3=q13.top().fi+q23.top().fi+q30.top().fi;
            maxn=max(max(sum0,sum1),max(sum2,sum3));
            ans+=maxn;
            if(maxn==sum0) {
                vis[q23.top().se]=3; In(q23.top().se);
                vis[q10.top().se]=0; In(q10.top().se);
                continue;
            }
            if(maxn==sum1) {
                vis[q13.top().se]=3; In(q13.top().se);
                vis[q20.top().se]=0; In(q20.top().se);
                continue;
            }
            if(maxn==sum2) {
                vis[q10.top().se]=0; In(q10.top().se);
                vis[q20.top().se]=0; In(q20.top().se);
                vis[q03.top().se]=3; In(q03.top().se);
                continue;
            }
            if(maxn==sum3) {
                vis[q13.top().se]=3; In(q13.top().se);
                vis[q23.top().se]=3; In(q23.top().se);
                vis[q30.top().se]=0; In(q30.top().se);
                continue;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

致谢名单

@WAPER4EVER 你在P5470的题解里的说法很具有启发性

@s_r_f 你在P5470的题解里的说法很具有启发性

@lyyi2003 你在CF436E的题解里的说法很具有启发性

还有一些，因为时间的问题，不记得了，抱歉。