一.什么是反悔贪心
顾名思义，反悔贪心就是两个操作：“反悔” + “贪心”。
一般来说，贪心仅能解出局部最优解。
那么在要求全局最优解时，我们就可以利用“反悔”这个操作解决。
反悔贪心的思想是：每次都进行操作，在以后有最优情况的时候再取消这次操作。
二.反悔贪心基本操作
一般来说，我们采用一个堆来存之前的贪心决策，堆顶是最劣决策。（想要让决策最优必然要撤销之前的最劣决策）
分两种情况：
-
符合某种条件时，推入堆，计算答案。
-
不符合某种条件时，与堆顶比较，做出操作。
接下来用一些例题来帮助大家理解这个算法。
三.反悔贪心例题
P3049 [USACO12MAR]Landscaping S
还有他的加强版P2748
可以算是比较板子的反悔贪心的题了。
保证 $0 \leq A_i,B_i \leq 10≤A $
有了这句话我们就可以一盆一盆来转移泥土
我们遍历每一个节点，更新 ans，ans表示到当前节点为止前面所有节点都满足要求的最小代价。
这样我们遍历完最后一个节点后，ans便是最终答案。
对于泥土不够的，我们先花费x代价添加泥土，对于泥土过剩的，我们先花费y代价移走泥土。
同时我们要维护两个堆 q1,q2
q1 存之前的添加泥土的操作
q2 存之前的移走泥土的操作
这样我们存下这些操作便于以后撤销。
堆的比较规则我们会在下面提到。
我们考虑两个花坛之间转移的情况。
情况一：当前花坛的泥土不够
我们设当前看到第 \(i\) 个花坛，并且第 \(i\) 个花坛泥土不够，我们除了选择补全泥土以外，还可以选择从之前泥土过剩的花坛中转移，所以我们要比较 从 \(j\) 花坛转移泥土至 \(i\) 花坛 与 移走 \(j\) 花坛泥土且补全 \(i\) 花坛泥土 两种决策哪个代价更小，我们要选取其中的代价小的作为最优决策。
我们来考虑转移的代价
因为我们是从之前泥土过剩的花坛中转移
所以有 \(j<i\)
因此
从 \(j\) 花坛转移泥土至 \(i\) 花坛花费代价： \(z \cdot (i-j)\)
而
移走 \(j\) 花坛泥土且补全 \(i\) 花坛泥土花费代价：\(x+y\)
因为我们 ans 的定义是前面所有节点都满足要求的最小代价，也就是说，此时 ans 的值是已经移走了 \(j\) 花坛泥土的代价，所以这两种决策对 ans 的贡献分别为：
从 \(j\) 花坛转移泥土至 \(i\) 花坛对ans的贡献： \(z \cdot (i-j)-y=z \cdot i-(z \cdot j + y)\)
移走 \(j\) 花坛泥土且补全 \(i\) 花坛泥土对 ans 的贡献：\(x\)
不难发现，\(z \cdot i\) 是定值，想要让转移的代价最小，我们要找到一个位置 \(j\) 满足：
-
该位置进行过移走泥土的操作
-
\(z \cdot j + y\) 最大
堆 q2 存的是之前的移走泥土的操作，所以 q2 内的位置均满足性质一，而我们只需让 q2 维护为一个使 \(z \cdot j + y\) 最大的大顶堆，这样我们每次取堆顶就是我们需要的位置 \(j\)。
接下来更新 ans ：
-
转移的代价更大，即 \(z \cdot i-(z \cdot j + y) >= x\)
ans+=x，并将当前操作加入 q1 -
转移的代价更小，即 \(z \cdot i-(z \cdot j + y) < x\)
ans+=z * i - (z * j + y)，并取出 q2 的堆顶，并将当前操作加入 q1（有可能 \(i\) 和 \(j\) 转移并非最优，所以要把这次也加入 q1，方便后面撤销）
情况二：当前花坛的泥土过剩
与情况一同理
设当前看到第 \(i\) 个花坛，并且第 \(i\) 个花坛泥土过剩，我们除了选择移走泥土以外，还可以选择转移到之前泥土不够的花坛中，所以我们要比较 从 \(i\) 花坛转移泥土至 \(j\) 花坛 与 移走 \(i\) 花坛泥土且补全 \(j\) 花坛泥土 两种决策哪个代价更小，我们要选取其中的代价小的作为最优决策。
我们来考虑转移的代价
因为我们是转移到之前泥土不够的花坛中
所以有 \(j<i\)
因此
从 \(i\) 花坛转移泥土至 \(j\) 花坛花费代价： \(z \cdot (i-j)\)
而
移走 \(i\) 花坛泥土且补全 \(j\) 花坛泥土花费代价：\(x+y\)
因为我们 ans 的定义是前面所有节点都满足要求的最小代价，也就是说，此时 ans 的值是已经补全了 \(j\) 花坛泥土的代价，所以这两种决策对 ans 的贡献分别为：
从 \(i\) 花坛转移泥土至 \(j\) 花坛对ans的贡献： \(z \cdot (i-j)-x=z \cdot i-(z \cdot j + x)\)
移走 \(i\) 花坛泥土且补全 \(j\) 花坛泥土对 ans 的贡献：\(y\)
不难发现，\(z \cdot i\) 是定值，想要让转移的代价最小，我们要找到一个位置 \(j\) 满足：
-
该位置进行过补全泥土的操作
-
\(z \cdot j + x\) 最大
堆 q1 存的是之前的补全泥土的操作，所以 q1 内的位置均满足性质一，而我们只需让 q1 维护为一个使 \(z \cdot j + x\) 最大的大顶堆，这样我们每次取堆顶就是我们需要的位置 \(j\)。
接下来更新 ans ：
-
转移的代价更大，即 \(z \cdot i-(z \cdot j + x) >= y\)
ans+=y，并将当前操作加入 q2 -
转移的代价更小，即 \(z \cdot i-(z \cdot j + x) < y\)
ans+=z * i - (z * j + x)，并取出 q1 的堆顶，并将当前操作加入 q2（有可能 \(i\) 和 \(j\) 转移并非最优，所以要把这次也加入 q2，方便后面撤销）
至此我们这道题的思路就讲完了。
code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100010;
int n,a[N],b[N],ans,x,y,z;
priority_queue<int> q2,q1;
signed main() {
cin>>n>>x>>y>>z;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
if(a[i]<b[i]){//情况一：当前花坛的泥土不够
for(int j=1;j<=b[i]-a[i];j++)//一盆一盆转移
if(q2.empty()||z*i-q2.top()>x){
ans+=x;
q1.push(z*i+x);
}else {
int g=q2.top();
ans+=z*i-g;
q2.pop();
q1.push(z*i+z*i-g);
}
}else if(a[i]>b[i]){//情况二：当前花坛的泥土过剩
for(int j=1;j<=a[i]-b[i];j++)//一盆一盆转移
if(q1.empty()||z*i-q1.top()>y){
ans+=y;
q2.push(z*i+y);
}else {
int g=q1.top();
ans+=z*i-g;
q1.pop();
q2.push(z*i+z*i-g);
}
}
}
cout<<ans;
return 0;
}