本文共 3229 字，大约阅读时间需要 10 分钟。
前言：最近写了很多关于堆模拟费用流的题，说通俗一点就是用(堆+后悔操作)去实现贪心。
例题：
例1：POJ-2431 Expedition
解析：这题应该是这类套路里面最简单的一道题了， 每经过一个加油站相当于拥有了在这个加油站加油的权力，那么将这个加油站的油加入堆，一旦以后油不够用了，就从堆中取出最大值加油，直到终点。
#include #include #include #include #include #include #include #define ll long long#define N 100010using namespace std;int a[N],b[N];struct Node { int a,b; bool operator < (const Node &x) const { return a
Q;int gi() { int x=0,o=1; char ch=getchar(); while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') o=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return o*x;}int main() { int n=gi(),ans=0,pos=0,L,oil; for(int i=1; i<=n; i++) p[i].a=gi(),p[i].b=gi(); sort(p+1,p+n+1); L=gi(),oil=gi(); for(int i=n; i>=0; i--) { a[i]=L-p[i].a,b[i]=p[i].b; int d=a[i]-pos; while(oil-d<0) { if(Q.empty()) {puts("-1");return 0;} oil+=Q.top(),Q.pop(),ans++; } oil-=d,pos=a[i],Q.push(b[i]); } printf("%d", ans); return 0;}
例2：K10.31-D1T2 angry
解析：这题仔细分析一下就可以发现与上一题很类似，如果用零钱会花费c[i]%100的零钱，如果用整钱会100-c[i]%100，可以发现每次都要减去一个c[i]%100，但是用整钱的话就相当于赔了愤怒值但赚了100块钱，于是每次贪心尽量地出零钱，零钱不够用了就在堆中找愤怒值最小的那一天用整钱。
#include #include #include #include #include #include #include #define ll long long#define N 100010using namespace std;ll ans;int w[N],c[N],out[N][2];struct Node { int i,v; bool operator < (const Node &x) const { return v>x.v; }};priority_queue Q;int gi() { int x=0,o=1; char ch=getchar(); while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') o=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return o*x;}int main() { int n=gi(),m=gi(); for(int i=1; i<=n; i++) c[i]=gi(); for(int i=1; i<=n; i++) w[i]=gi(); for(int i=1; i<=n; i++) { if(c[i]%100==0) out[i][0]=c[i]/100,out[i][1]=0; else { if(m>=c[i]%100) { m-=c[i]%100; out[i][0]=c[i]/100; out[i][1]=c[i]%100; Q.push((Node){i,w[i]*(100-c[i]%100)}); } else { Q.push((Node){i,w[i]*(100-c[i]%100)}); Node u=Q.top(); Q.pop(); ans+=w[u.i]*(100-c[u.i]%100); m+=100-c[i]%100; out[u.i][0]=(c[u.i]+99)/100,out[u.i][1]=0; if(u.i!=i) out[i][0]=c[i]/100,out[i][1]=c[i]%100; } } } printf("%lld\n", ans); for(int i=1; i<=n; i++) { printf("%d %d\n", out[i][0],out[i][1]); } return 0;}
例3：K11.1-D2T2 trade
解析：首先这题很容易想到dp，但是只能做到1000，对于\(10^5\)就需要用到更高效的解法——堆模拟费用流。
具体到这道题来说就是一旦有利润那么就直接算利润，如果在后面的利润更大，那么用后悔操作可以获得更大的利润。
后悔操作：
1、当前股票比堆顶小，买入。
2、当前股票比堆顶大，卖出，并将当前股票入堆两次，一次相当于是用来实现“后悔”，方便算出将别人卖出的代价，另一次则是将自己卖出。
#include #include #include #include #include #include #include #define ll long long#define RG register#define N 100010using namespace std;int a[N];priority_queue ,greater > Q;inline int gi() { int x=0,o=1; char ch=getchar(); while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') o=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return o*x;}int main() { ll ans=0; int T=gi(),n,tot=0; while(T--) { n=gi(),ans=0; for(RG int i=1; i<=n; i++) a[i]=gi(); while(!Q.empty()) Q.pop(); for(RG int i=1; i<=n; i++) { Q.push(a[i]); if(Q.top()