反悔贪心的应用

目录：

• 反悔贪心的解释
• 反悔贪心的分类
  1.反悔自动机
  2.反悔堆
• 例题及应用

一 反悔贪心的解释

$\space\space$贪心本身是没有反悔操作的 贪心求的就是当前的最优解但当前的最优解有可能是局部最优解，
而不是全局最优解 这时候就可以考虑反悔操作
$\space\space$ 反悔操作 指的就是这一步的贪心不是全局最优解 我们就退回一步(人工或自动判断) 换一种贪心
策略 按照 判断方式的不同分为 反悔自动机 和 反悔堆两种方式

二反悔贪心的分类

    1.反悔自动机：

    即设计一种反悔策略，使得随便一种贪心策略都可以得到正解。
基本的设计思路是：每次选择直观上最接近全局最优解的贪心策略，若发现最优解不对，就想办法自动支持反悔策略（这
就是自动机的意思）具体题目具体分析。一般需要反悔自动机的题都是通过差值巧妙达到反悔的目的。

    2.反悔堆：

    即通过堆（大根堆、小根堆）来维护当前贪心策略的最优解，若发现最优解不对，就退回上一步，更新最优解。
由于堆的性质，使得堆的首数据一定是最优的，这就可以实现快速更新最优解。

反悔自动机例题

• CF865D Buy Low Sell High

题意

$\space\space$给定接下来数天的股票价格 每次可以购买或者出售一次股票 要求求得最大的获利多少

解析

$\space\space$在该题中 我们最先想到的贪心策略就是在价格少的时候购买 价格高的时候出售 但是在该处贪心证明的
时候明显不成立 所以我们需要考虑后悔贪心的操作 我们对每次出售股票给定一个后悔值 并在接下来的情况进行判断 例如该题中 我们对于每一个形如「在第 i 天买入，在第 j 天卖出」的决策，假想出一个价格为 valval的物品，使得「在第 i 天买入，在第 j 天卖出，同时买入这个价格为 val 的物品，并在第 k 天卖出」，等价于「在第 i 天买入，在第 k 天卖出」。这样，我们选择买入这样一个物品，也就相当于撤销了「在第 i 天买入，在第 j 天卖出」这个决策，而改为「在第 i 天买入，在第 k 天卖出」，反悔操作得以实现。
$\space\space$ 那么这个加值val究竟是多少呢？设第i天的价格为a[i] 则有a[j] - a[i] + a[k] -val = a[k] - a[i]等价于val = a[j] 于是 我们便涉及出了一个新的算法 维护一个可重集合 代表[可选的物品的价格] 从前向后遍历每一天对于第i天 找到集合中最先的元素aj 并向集合插入当前元素a[i] 代表a[i]这一天的价格可以选择 如果a[i] > a[j] 代表在a[i]处买进 在a[j]处卖出 我们ans 加上这个初步差值 并在想集合中插入val代表反悔值 并将a[j]删除集合 我们可以用堆来维护这个集合最小值

上面的等式即被称为反悔自动机的反悔策略，因为我们并没有反复更新全局最优解，而是通过差值消去中间项的方法快速
得到的全局最优解。

模拟实现

eg:10 5 4 7 9 12 6 2 10
我们在直到遍历第4天的时候 此时ai> aj[代表有差价 有利可图] 我们对ans += a[i] - a[j] = 3
并插入我们的反悔值 value = 7 同理在9处我们ans += 4 添加value = 9 在12的时候我们ans += 12 - 7 = 5 并且
value = 12 最后在a[i] = 10时 我们ans += 10 - 2 = 8 最后结果ans = 20 即为所求

#include<iostream>
#include<queue>
using namespace std;
typedef long long LL;
int main()
{
    priority_queue<int, vector<int>, greater<int> > q;//小根堆 维护最小值
    LL n;
    cin >> n;
    LL ans = 0;
    for(int i = 0; i < n; i ++)
    {
        LL x;
        cin >> x;
        if(q.size() && q.top() < x)  ans += x - q.top(), q.pop(), q.push(x);
        q.push(x);
    }
    cout << ans << endl;
}

洛谷p1484种树

题意

$\space\space$ 给定n个数求得最多m个数的最大和 要求所选的数不能相连

解析

 本题我能很容易相到DP解法 不过鉴于数据范围的过大 所以我们不能局限于DP方法 此处我们引述一个新的
知识点---后悔贪心 
 后悔贪心顾名思义 基于贪心的可后悔的方法 什么意思呢 比如本题中 给定 8 9 8 1四个数 按照贪心来讲
我们会优先选择9这个最大的数 然后导致我们接下来只能选择1这个数 但此时我们这种思想是错误的 真实的最大值其实是8 + 8
  那么我们只能退而求其次 取两个次大值8 + 8
  而后悔贪心是怎样呢 贪心的目的是从局部最优解 进而推到全局最优解 那么在后悔贪心中 我们对每次选取
新增一个后悔选项 我们在实际贪心中发现在对下一个数进行判断时候 我们要么选择a[i]与另个数 要么选择a[i-1]和a[i+1]
   比如针对 8 9 8 1我们按照贪心的想法 先选择9 这个最大值 其次我们增加一个后悔值 x = 8 + 8 - 7, 并按照题述
要求9 两边的8均标记不能选择 所以在第二轮循环选取中 最大值是左侧的8 此时该数被标记不能选择 在其次出现
的是右侧的8 此时同样标记不能选择 那么接下来的最大值便是7这个新加的数 那么最大和便为9 + 7 = 16 
7 代表什么意思 代表的就是当9不选择后的反悔选择 换句话说就是在新的一轮(可以多有一个选择数的机会)下 不选择9 
而去选择8 + 8 的选项

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define N 500007
#define INF 0x3f3f3f3f
typedef long long LL;
using namespace std;
struct Place
{
    LL v, l, r;
}p[N];

struct Node
{
    LL v, id;
    bool operator <(Node t) const 
    {
        return v < t.v;
    }
};

LL n, m, ans, last;
bool st[N];
priority_queue<Node> q;

void del(int x)
{
    p[x].l = p[p[x].l].l;
    p[x].r = p[p[x].r].r;
    p[p[x].l].r = x;
    p[p[x].r].l = x;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        p[i].v = x;
        p[i].l = i - 1;
        p[i].r = i + 1;
        q.push((Node){p[i].v, i});
    }

    for(int i = 1; i <= m; i ++)
    {
        while(q.size() && st[q.top().id]) q.pop();
        if(!q.size() || q.top().v < 0) break;
        Node t = q.top();
        q.pop();
        ans += t.v;

        st[p[t.id].l] = st[p[t.id].r] = true;
        p[t.id].v = p[p[t.id].l].v + p[p[t.id].r].v - p[t.id].v;

        q.push((Node){p[t.id].v, t.id});
        del(t.id);
    }  
    cout << ans << endl;
}

反悔堆即其应用

USACO09OPEN 工作调度Work Scheduling

题意

有 n 项工作，每 i 项工作有一个截止时间 Di ，完成每项工作可以得到利润 Pi ，求最大可以得到多少利润。

解析

$\space\space$本题切勿不可直接按照截止时间为第一关键字 利润为第二关键字排序 因为本题中相同一个截止范围内
利润多的可以将之前的工作中利润小的给替代 也就是相同截止时间下 并不一定只能选择一个
$\space\space$举个例子来说 针对[1, 10][2, 1][3, 10][3, 10]我们发现 在3截止下的两个任务利润都很高
我们可以用一个任务替代截止时间为2的任务 从而获得最大收益
$\space\space$所以我们先对整个工作进行截止时间的排序 按照截止时间从小到大排序 并建立一个堆用来维护
利润的最小值 因为按照截止时间排序 那么后续的截止时间获得的利润即可直接替代之前时间下的利润最小而不
需要考虑时间因素 故而 我们对后续插入的收益进行一个堆的判断并计算

伪代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
typedef long long LL;
using namespace std;
const int N = 1e5 + 10;
struct Node
{
    LL t, v;
}q[N];
bool cmp(Node a, Node b)
{
    if(a.t != b.t) return a.t < b.t;
    return a.v < b.v;
}

priority_queue<int,vector<int>,greater<int> > h;

int n;
LL ans;

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
        cin >> q[i].t >> q[i].v;
    sort(q, q + n, cmp);

    for(int i = 0; i < n; i ++)
    {
        if(q[i].t <= h.size())//每个时间段都有了 开始舍弃小的获得大的
        {
            if(q[i].v > h.top())
            {
                ans -=h.top();
                h.pop();
                ans += q[i].v;
                h.push(q[i].v);
            }
        }
        else //还有空闲的时间段 直接加入
        {
            h.push(q[i].v);
            ans += q[i].v;
        }
    }

    cout << ans << endl;

}

试题推荐

建筑抢修 反悔堆
(国集)种树 反悔自动机
种树 反悔自动机
数据备份 反悔自动机

借鉴参考

nth_element