首页 > 其他分享 >反悔贪心学习笔记

反悔贪心学习笔记

时间：2024-05-22 18:12:25浏览次数：26  
标签：int 笔记 反悔 任务 最优 我们 贪心

本文仅用于笔者关于反悔贪心的学习笔记，反悔贪心是笔者在一场$div4$中遇到的问题，故来学习一番

【学习笔记】反悔贪心

 

1、什么是反悔贪心？

贪心本身是没有反悔操作的，贪心求的就是当前的最优解。但当前的最优解有可能是局部最优解，而不是全局最优解，这时候就要进行反悔操作。

另外的来自蒟蒻dalao的解释：

众所周知，正常的贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。也就是说我们的每一步都是站在当前产生的局面上所作出的最好的选择，是没有反悔操作的。

不加反悔的一直朝着当前局面的最优解走很可能导致我们被困在局部的最优解而无法到达全局的最优解，就好像我们爬山就只爬到了一座山的山顶却没有到整片山的最高处：

1.png

但是反悔贪心允许我们在发现现在不是全局最优解的情况下回退一步或若干步采取另外的策略去取得全局最优解。就好像我们站在的一座山的山峰上，看到了还有比我们现在所在位置还高的山峰，那我们现在就肯定不是在最高的地方了，这时我们就反悔——也就是下山再爬上那座更高的山：

2.png

这就是反悔贪心的大致思路。根据反悔记录操作的不同，反悔贪心又分为反悔堆和反悔自动机。

总的来说：反悔操作指的是这一步的贪心不是全局最优解，我们就退回去一步（人工或自动判断），换一种贪心策略。按照判断方式的不同可以分为反悔自动机和反悔堆两种方法。

  1. 反悔自动机：

    即设计一种反悔策略，使得随便一种贪心策略都可以得到正解。

    基本的设计思路是：每次选择直观上最接近全局最优解的贪心策略，若发现最优解不对，就想办法自动支持反悔策略。（这就是自动机的意思）

    具体题目具体分析。一般需要反悔自动机的题都是通过差值巧妙达到反悔的目的。

  2. 反悔堆：

    即通过堆（大根堆、小根堆）来维护当前贪心策略的最优解，若发现最优解不对，就退回上一步，更新最优解。

    由于堆的性质，使得堆的首数据一定是最优的，这就可以实现快速更新最优解。

2、例题以及代码

反悔堆

用时一定模型

USACO09OPEN 工作调度Work Scheduling

Description:

有 \(n\) 项工作，每 ii 项工作有一个截止时间 \(D_i\) ，完成每项工作可以得到利润 \(P_i\) ，求最大可以得到多少利润。

Method:

尽管这道题直接理解会感觉简单，实则不然。

对于简单贪心：

第一种贪心是开一个桶，对于每一个截止日期我们都只保留能产生价值最大的任务去做，其余的不去做。这种方法很明显是错误的，我们可以举出一个例子来否定这个策略。比如我们只有两个任务A和B，A任务的截止日期是3，价值是3；B的截止日期是3，价值是1。按照我们的贪心策略，我们就舍弃B选择A，但是实际上，我们可以在时间2去做B，时间3去做A这样就可以全都要，明显比只做A会好得多，所以这种贪心策略是不可取的。

第二种贪心就更加明智一点，我们都有一种直觉那就是先完成比较紧急的任务亦或者说先完成截止日期靠前的任务会更加优。所以我们就按照截止日期(从小到大)为第一关键字，价值(从大到小)为第二关键字进行排序，然后顺序遍历每个任务，能做就做，不能做(当前已安排任务数=当前任务的截止日期)就直接抛弃。这样做看起来很有道理，但实际上有有可能到后期都是高报酬的工作（但由于前期做了太多价值很低的任务导致都超时做不了了）就会让答案不是很优秀。比如我们举个例子。加入我们有四个任务A、B、C、D.其中A任务的截止日期为1，价值为2；B的截止日期为1，价值为1；C的截止日期为2，价值为5；D的截止日期为2，价值为6。按照我们现在的贪心策略，我们会排序后按照ABDC的顺序进行考虑，然后选择AD这两个任务去完成最后结果是8。但实际上，如果我们不去做A，而是把做A的时间拿去做C，这样我们最后的结果就是11是优于我们的贪心答案的。

为什么会出现这样的问题呢？是因为到了后期，我们见到了很多高回报的工作但是能做的却很有限了，这又是因为前期做了很多价值很低的任务，换句话说我们可能会后悔前期做了些低报酬的工作。那我们能不能反悔，也就是退掉之前低报酬的工作用那个时间去完成高报酬的工作呢？这就要用到我们的反悔堆。

当然我们还有第三种贪心，以价值为关键字从大到小排序，假如我们考虑第i个任务做不做，如果从1∼t[i]（第i个任务的截止时间） 没有塞满，那就尽量咕到最后一个空位做，正确也是显然的，但是直接暴力是 \(O(n^2)\) 的。然后我们发现找空位的过程可以优化，加入树状数组，二分位置判断即可，时间复杂度 \(O(nlog^2n)\) 即可以通过。

反悔贪心：

假如满足题设条件（即没有超出截止时间）就分成两种情况：若当前的最优解比原来的最优解（堆顶）更优秀，我们就更新全局最优解，把原来的最优解丢出去，再把当前的最优解放进去（即反悔策略）；反之，就不管了。假如不满足特设条件，就把当前的最优解丢进堆里，更新全局最优解即可。

// RioTian 21/03/10 学习自 蒟蒻dalao
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct node {
    int deadline, value;
    //重载<号的定义，规定堆为关于价值的小根堆
    bool operator<(const node &v) const {
        if (value > v.value) return true;
        return false;
    }
} a[110000];
// 使用优先队列代替手写堆(节省Coding时间)
priority_queue<node> q;
int n;
ll ans = 0;

//自定义排序函数，将任务按截止时间从小到大排序
bool cmp(node x, node y) {
    if (x.deadline < y.deadline) return true;
    return false;
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].deadline >> a[i].value;
    sort(a + 1, a + 1 + n, cmp);
    for (int i = 1; i <= n; ++i) {
        //如果当前决定做的任务数小于截止日期也就是还有时间做当前任务
        if (a[i].deadline > q.size()) {
            ans += a[i].value;
            q.push(a[i]);
        } else {
            if (a[i].value > q.top().value) {
                ans -= q.top().value;
                q.pop();
                q.push(a[i]), ans += a[i].value;
            }//反悔操作 
        }//考虑是否反悔，不做之前做的任务 
    }
    cout << ans << "\n";
    return 0;
}

价值一定模型

模型总结来自蒟蒻dalao，万分感谢！

Description:

我们再来考虑这样一个问题，我们有 \(n\) 个任务( \(n≤1e5\) )，并且每个任务都有两个属性——截止日期和完成耗时。在截止日期前完成任务就可以得到这个任务产生的价值。在同一时间我们只能去做一个任务。所有任务的价值都是一样的，问我们最后最多能完成多少个任务。

算法讲解

有了刚刚那题的基础，我们也很容易可以考虑到反悔贪心的反悔堆模型上。由于我们需要反悔操作，而反悔操作是建立我们能够反悔——不做之前决定做的任务而去做当今决定做的任务，所以首先我们肯定还是要按照截止日期从小到大进行排序。

在我们上面讲到的用时一定的模型中，我们用堆维护“性价比”最低的任务也就是我们价值最低的任务用于反悔操作。在这个问题中，我们同样用堆去维护“性价比”最低的任务。由于每个任务的价值是一定的，所以我们性价比最低的任务就是耗时最长的任务，如果我们不做耗时比较长的任务去做耗时比较短的任务，我们就能留下更多的时间给后面的任务，又由于每个任务的价值是一样的，所以这样做的正确性也是显然的。

所以具体来说我们就开一个大根堆维护已选任务的时间，堆顶就是耗时最长的任务。我们顺次考虑排序后的每个任务，当前决定要做的任务的总耗时加上现在这个任务的耗时小于等于现在这个任务的截止时间，那我们就直接做，把现在这个任务丢进堆里，总耗时加上现在这个任务的耗时就可以了。但如果当前决定要做的任务的总耗时加上现在这个任务的耗时大于现在这个任务的截止时间呢，我们就考虑是否进行反悔操作替换决定做的任务。我们看一看堆顶任务的耗时和现在这个任务的耗时，如果堆顶任务的小那就不替换；如果当前任务的耗时小，我们就用当前任务替换掉堆顶任务就好啦。

模板代码

这道题也是有模板题的，题目是[JSOI2007]建筑抢修，下面附上模板代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct node {
    int deadline, time;
    //重载<号的定义，规定堆为关于耗时的大根堆
    bool operator<(const node &v) const {
        if (time < v.time) return true;
        return false;
    }
} a[160000];
// 使用优先队列代替手写堆(节省Coding时间)
priority_queue<node> q;
int n;
ll last = 0;

//自定义排序函数，将任务按截止时间从小到大排序
bool cmp(node x, node y) {
    if (x.deadline < y.deadline) return true;
    return false;
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].time >> a[i].deadline;
    sort(a + 1, a + 1 + n, cmp);
    for (int i = 1; i <= n; ++i) {
        //如果决定做的任务耗总时加上当前任务耗时小于等于当前任务截止时间
        if (a[i].deadline >= last + a[i].time) {
            last += a[i].time;
            q.push(a[i]);
        } else {
            //如果堆顶耗时大于当前考虑任务的耗时
            if (a[i].time < q.top().time) {
                last -= q.top().time;
                q.pop();
                q.push(a[i]), last += a[i].time;
            }  //反悔操作
        }      //考虑是否反悔，不做之前做的任务
    }
    cout << q.size() << "\n";
    return 0;
}

反悔自动机

相比于反悔堆，反悔自动机更加高级一点，它能够自动的维护我们反悔的操作，通常适用于带限制的决策问题上。

举例：假如我们有四个数ABCD，AB当中只能选一个，CD当中只能选一个，问我们最后能收获的最大价值是多少。

反悔自动机样例

假如刚开始我们选的是AC，那我们就可以把AC先删掉，把的值B变成B-A，D的值变成D-C，接下来的选择不考虑任何束缚。这样如果我们接下来再去选B，那这时我们选的值其实是B-A，加上之前选的A，相当于我们选了B没有选A，这就完成了返回操作——通过修改关联点的值让我们做到不选之前决定选的点而去选现在这个点。

这就是反悔自动机的大致思路。具体的反悔自动机又分为堆反悔自动机和双向链表反悔自动机两种，这样讲可能有点抽象，我们下面通过几个例题来看看反悔自动机的具体运用。

堆反悔自动机

CF865D Buy Low Sell High（堆反悔自动机）

Description:

已知接下来 \(n\) 天的股票价格，每天可以买入当天的股票，卖出已有的股票，或者什么都不做，求 \(n\) 天之后最大的利润。

Method：

我们先从简单的贪心开始考虑。首先我们可以贪心地对于每一天 i，如果我们可以卖出，那么贪心的选择之前的价格最小的一天 j，然后若 \(P_j &lt; P_i\) 就可以在 j 天买入一股，然后在第 i 天卖出，这时候就仅需要一个 priority_queue 就可以了。

但是还有一个问题，如何考虑下面这组数据呢？

1 2 5

可以发现，若贪心处理，则仅会在第 1 天买入一股，并在第 2 天卖出，赚到了 1 元。但是若将第 1 天的股票在第 3 天卖出，则可以获得高达 4 元的利润，比原答案不知道高到哪里去了。

所以我们尝试去考虑设计一种反悔策略，使所有的贪心情况都可以得到全局最优解。（即设计反悔自动机的反悔策略）

定义 \(C_{buy}\) 为全局最优解中买入当天的价格，\(C_{sell}\) 为全局最优解中卖出当天的价格，则：

 

\[C_{sell} - C_{buy} = (C_{sell} -C_i) + (C_i - C_{buy}) \]

 

\(C_i\) 为任意一天的股票价格

即我们买价格最小的股票去卖价格最大的股票，以期得到最大的利润。我们先把当前的价格放入小根堆一次（这次是以上文的贪心策略贪心），判断当前的价格是否比堆顶大，若是比其大，我们就将差值计入全局最优解，再将当前的价格放入小根堆（这次是反悔操作）。相当于我们把当前的股票价格若不是最优解，就没有用，最后可以得到全局最优解。

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

Code:

struct node {
    int value;
    // 重载<号的定义，规定堆为关于价值的小根堆
    bool operator<(const node &b) const {
        if (value > b.value) return true;
        return false;
    }
} a[330000];
priority_queue<node> q;
int n;
ll cnt = 0;

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].value;

    for (int i = 1; i <= n; ++i) {
        q.push(a[i]);  //用于贪心买价格最小的股票去买价格最大的股票
        //假如当前的股票价格不是最优解
        if (q.size() && q.top().value < a[i].value) {
            cnt += a[i].value - q.top().value;  //将差值计入全局最优解
            // 将已经统计的最小的股票价格丢出去，并执行反悔策略：将当前的股票价格再放入堆中，即记录中间变量（等式中间的Vi)
            q.pop(), q.push(a[i]);
        }
    }
    cout << cnt << "\n";
    return 0;
}

双向链表反悔自动机

BZOJ2151 种树（双向链表反悔自动机）

Description:

有 \(n\) 个位置，每个位置有一个价值。有 \(m\) 个树苗，将这些树苗种在这些位置上，相邻位置不能都种。求可以得到的最大值或无解信息。

Method：

先判断无解的情况，我们显然可以发现，若 \(m&gt;\frac{n}2\) ，则是不能在合法的条件下种上 m 棵树的，故按题意输出Error!即可。

假如有解的话，我们可以很轻松的推出贪心策略：在合法的情况下选择最大的价值。

显然上面的策略是错误的，我们选择了最大价值的点，相邻的两个点就不能选，而选择相邻两个点得到的价值可能更大。

考虑如何设计反悔策略。

我们同样用差值来达到反悔的目的。假设有 \(A ，B ，C ，D\) 四个相邻的点（如图）。

\(A\) 点的价值为 \(a\) ，其他点同理。若

 

\[a + c > b + d \]

 

则：

 

\[a + c - b > d \]

 

假如我们先选了 \(B\) 点，我们就不能选 \(A\) 和 \(C\) 两点，这显然是不对的，但我们可以新建一个节点 \(P , P\) 点的价值为 $a+c−b $，再删去 \(B\) 点。（如图，红色的是删去的点，橙色的新建的点)

img

下一次选择的点是 P 的话，说明我们反悔了（即相当于 B 点没有选），可以保证最后的贪心最优解是全局最优解。

如何快速插入 P 点和找出是否选择 P 点呢？我们可以使用双向链表和小根堆，使得最终在 \(O(nlog⁡n)\) 的时间复杂度下快速求出全局最优解.

注意点：

  • 一定要记录这个点选没有选过，假如已经选过了，就从堆中丢出去；
  • 1 与 n 是相邻的，一定要特判一下；
  • 双向链表一定不要写挂了；
  • 一定要先将新建的点的价值存入一开始的价值数组，再丢进堆里；（不然会卡数据）
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e6 + 10;
struct node {
    int val, id;
    bool operator<(const node& x) const { return val < x.val; }
} now, x;
ll val[N];              // 价值
ll vis[N], l[N], r[N];  // vis记录是否删除,l、r为双向链表的左右点

int t, n, m;
ll ans = 0;
priority_queue<node> q;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> val[i];
    while (q.size()) q.pop();

    // 初始化堆
    for (ll i = 1; i <= n; ++i) {
        now.id = i, now.val = val[i];
        vis[i] = 0;
        q.push(now);
    }

    // 处理双向链表
    for (int i = 2; i <= n; ++i) l[i] = i - 1;
    for (int i = 1; i <= n; ++i) r[i] = i + 1;

    l[1] = r[n] = 0;

    for (int i = 1; i <= m; ++i) {
        x = q.top(), q.pop();
        while (vis[x.id] == 1) {  //找到一个没有被删除的值最大的点
            x = q.top(), q.pop();
        }

        if (x.val < 0) break;
        ans += x.val;
        if (l[x.id] != 0) vis[l[x.id]] = 1;  //删除左边的点
        if (r[x.id] != 0) vis[r[x.id]] = 1;  //删除右边的点

        if (l[x.id] != 0 && r[x.id] != 0) {
            now.id = x.id;
            now.val = val[x.id] = val[l[x.id]] + val[r[x.id]] - val[x.id];

            r[l[l[x.id]]] = x.id;
            l[x.id] = l[l[x.id]];
            l[r[r[x.id]]] = x.id;
            r[x.id] = r[r[x.id]];
            q.push(now);
        } else if (l[x.id])
            r[l[l[x.id]]] = 0;
        else
            l[r[r[x.id]]] = 0;
    }
    cout << ans << "\n";
    return 0;
}
   

标签：int,笔记,反悔,任务,最优,我们,贪心
From： https://www.cnblogs.com/o-Sakurajimamai-o/p/18206814

相关文章

  • 学习笔记：集合幂级数与 FWT
    集合幂级数集合到整数设\(n\)元集\(A=a_1,a_2,\cdots,a_n\)，定义\(A\)的幂集\(2^{A}=\{S\midS\subseteqA\}\)到整数集\(\mathbb{Z}\)的映射\(\text{id}\)为：若\(S=\{a_{i_1},a_{i_2},\cdots,a_{i_k}\}\)，则\(\text{id}(S)=\sum_{j=1}^{k}2^......
  • 经常出差用哪些办公软件记录工作？可多设备同步使用的便签笔记软件
    对于许多职场人士来说，出差已成为工作常态。在旅途中，如何高效处理工作，确保信息不遗漏，成为了一个不小的挑战。那么，对于经常需要移动办公的我们，哪款办公软件才是最佳选择呢？可多设备同步使用的便签笔记软件是哪款？答案就是——敬业签，一款强大而便捷的便签笔记软件。它的强大之处在于其......
  • 学习笔记：Miller-Rabin 与 Pollard-Rho
    Miller_Rabin首先考虑方程\(x^2\equiv1\pmodn\)。可以写成\((x+1)(x-1)=kn\)。当\(n\)为素数时，只可能\(n\midx+1\)或\(n\midx-1\)，反之合数不满足。得到结论：在模素数意义下，一个数的平方等于\(1\)当且仅当这个数同余于\(1\)或\(-1\)。我们知道，......
  • Mars的学习笔记（更新中）
    前言这篇文章主要用来总结我之前所学的算法，以更好地复习。希望大家在看时能理解我所说的话（包括未来的我）算法大典KMPKMP是一个强大的字符串搜索算法，可以在线性的复杂度下将所需要的子串位置精确的找出。它的最大特点就是搜索是不会回溯。朴素思想给出两个字符串ababababbab......
  • 《梦断代码》阅读笔记3
        对这本书的阅读终于要结束了，“梦断代码”：代码阻断了梦的实现吗？一直以为，计算机是万能的，自己想的都可以通过代码实现。在接触代码以后的这段时间里，我的想法改变了。代码可以实现自己的想法，但是怎么实现却要看自己了，算法自己思考，计算机只负责运行，运行通过就说明算法通过......
  • Java学习笔记（一）
    Java学习笔记（一）字节计算机存储的最小计量单位：byteB存储单位换算：8bit=1B(byte)1024B=1KB1024KB=1MB1024MB=1GJava环境jvm与跨平台：jvm——运行Java程序的假想计算机跨平台——Java代码能在不同操作系统上运行两者关系——想要实现跨平台，需要安装对应版本......
  • Asp-Net-Core开发笔记：使用原生的接口限流功能
    前言之前介绍过使用AspNetCoreRateLimit组件来实现接口限流从.Net7开始，AspNetCore开始内置限流组件，当时我们的项目还在.Net6所以只能用第三方的现在都升级到.Net8了，当然是得来试试这个原生组件体验后：配置使用都比较简单，不过功能也没有AspNetCoreRateLimit那么灵活......
  • ZooKeeper论文笔记.18205343
    概要是什么：ZooKeeper是一个分布式系统的基础构件（协调内核），分布式应用（如RocketMQ）可以使用ZooKeeper来处理分布式系统协同的各个方面，比如可以使用它来实现leader选举、分布式锁等等，分布式应用可以使用它暴露的API实现各种类型的协同原语（考虑Java中的AQS）。它让分布式应用的设计者无需......
  • 《人月神话》阅读笔记
    终于有幸拜读了《人月神话》这部业内经典著作。整体来说，本书的主线——人月神话、没有银弹在现今的软件工程管理领域依然属于有效的基础理论。不过有些东西确实过时了，比方说文档的管理，现在已经有了svn或者在线文档。提到调试的复杂性，现在的集成环境把调试变得非常容易。读完之后才......
  • 《人月神话读书笔记二》
    贯彻执行即使是大型的设计团队，设计结果也必须由一个或两个人来完成，以确保这些决定是一致的。允许体系结构师对实现人员的询问做出电话应答解释是非常重要的，并且必须进行日志记录和整理发布。对于存有疑问的实现人员，应鼓励他们打电话询问相应的结构师，而不是一边自行猜测一边工作......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99