标签：node return int long 反悔 const KuonjiCat 贪心

反悔贪心

本蒟蒻在做题时被卡，看题解发现用反悔贪心，遂搜罗资料，得有此篇

part.1

什么是反悔贪心？

简单的例子，我有一个只能装3个物品的背包，我要从n个价值由小到大的物品中选出3个最大的装进包里，但只能从头往后选，假如我此刻的包内物品价值为1 2 3，而我要面对的下一个物品的价值为4，那么我就要丢掉我包里价值最小的物品，也就是反悔，然后将这个价值更大的4放入背包内，这便是反悔贪心

也就是说，在局部范围内做出的最优决策对于全局来说并不适用，于是我们就需要反悔的操作，尽可能达成最优解

part.2

堆

此处我们需要用到堆的数据结构，我们可以手写一个堆出来，也可以使用stl中的优先队列

在此处提一下优先队列

优先队列（priority_queue) 是一种stl容器，他与正常的队列不同的是，我们可以自定义队列内元素的优先级

优先队列只维护队头的元素

priority_queue<data type> pq;//建堆操作
//第一种写法
//默认为大根堆
struct cmp{
    bool operator ()(const int & u, const int & v) const
    {
        return u > v;
    }
};
//若要使用小根堆将大于号换成小于即可
//当使用自己定义的结构体时重载小于号
struct Node{
    int x, y;
    bool operator < (const Node &u)const
    {
        return x == u.x ? y < u : u < x;
    }
};
//另外一种写法，比第一种方便很多
struct node {
    int x, y;
    bool operator < (const node &v) const
    {
        if(y > v.y)return(true);
        else return(false);
    }//重载<号的定义，规定堆为关于y的小根堆 
};

part.3

反悔贪心的写法

一般情况下有两种：反悔堆与反悔自动机

两种模型：用时一定模型，价值一定模型

我们先来介绍一下反悔堆

1.反悔堆

用时一定模型

P2949 [USACO09OPEN] Work Scheduling G

简要题意，n项工作，每个工作都有一个截止日期已经完成后的回报，完成这个工作要花费一个单位的时间

简单的贪心思想在这并不成立，可以举的例子很多，此处就不提了

我们只考虑最优的解法：这道题的一个优质解法就是使用反悔堆

因为题目中说，我们可以在任意时间完成一份任意的工作（前提是工作没有逾期

那么我们在同一时间内，既可以选择完成a也可以选择完成b工作

题目的思路大致如下：先排序，考虑维护一个小根堆

如果说我们能通过舍弃价值低的工作来完成报酬更高的工作

换句话说，就是堆顶的元素要比接下来要面对的元素价值小，就舍弃这个堆顶，把新的工作放进来

堆内所有元素之和就是答案

#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);
        else return(false);
    }
}a[110000];
priority_queue<node> pq;

bool cmp(node x, node y){
    if(x.deadline < y.deadline) return(true);
    else return(false);
}
ll ans;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i].deadline >> a[i].value;
    sort(a + 1, a + n + 1, cmp);
    
    for(int i = 1;i <= n;i ++) {
        if(pq.size() < a[i].deadline){
            ans += a[i].value;
            pq.push(a[i]);
        }//截止日期没到，就还能做任务
        else {
            if(a[i].value > pq.top().value){//如果接下来的工作价值更大，就反悔
                ans -= pq.top().value;pq.pop();
                ans += a[i].value;
                pq.push(a[i]);
            }
        }
    }
    cout << ans;
    return 0;
}

价值一定模型

P4053 [JSOI2007] 建筑抢修

简要题意：n项工作，每个工作有一个完成花费的时间以及截止时间，工人可以选择做任意一个任务，但只有修理完才能去做下一个任务，问最多能修多少个建筑

与上一道题不同，这次每份工作所花费的时间不同，但是价值是相同的

那么类似的思路，这次我们考虑使用一个大根堆来维护堆顶，堆顶的元素就是堆内目前耗时最长的工作

如果有比它耗时短的，就pop掉，然后将新的push进来

#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);//大根堆用小于号
        else return(false);
    }
}a[160000];
priority_queue<node> pq;

bool cmp(node x, node y){
    if(x.deadline < y.deadline) return(true);
    else return(false);
}//截止日期从小到大排序
ll last;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i].Time >> a[i].deadline;
    sort(a + 1, a + n + 1, cmp);
    
    for(int i = 1;i <= n;i ++) {
        if(a[i].deadline >= last + a[i].Time){
            last += a[i].Time;
            pq.push(a[i]);
        }//如果说，这次工作完成的耗时与之前相加没超时，那么就push进来
        else {
            if(a[i].Time < pq.top().Time){//如果说接下来完成时间更小，就push入堆中
                last -= pq.top().Time;pq.pop();//先pop在push
                last += a[i].Time;
                pq.push(a[i]);
            }
        }
    }
    cout << pq.size();//最后输出堆内元素的数量即可
    return 0;
}

2.反悔自动机

问题：你现在有A, B, C , D四个数，每次只能从中AB中选择一个CD中选择一个，问怎么选价值最大

思路：我先选A 和 C，然后将B, D的值分别更新为B - A和D - C

那么我们接下来继续选，如果说选择了B，那么实际上选择的是B - A，再加上之前的A，就相当于我们只选择了B

也就是相当于反悔了

反悔自动机的基本思想就是，通过修改关联点的值让我们避免去选择之前决定过的点

堆反悔自动机

https://codeforces.com/contest/865/problem/D

买股票问题：已知后面n天每天的股票价格，在每一天里，你都可以买入一份股票并卖出一份股票，问n天之后你的最大收益为多少（n天之后你持有的股票数量应当为0）

设计反悔自动机的反悔策略，使所有的贪心情况都可以得到最优解

定义在Pbuy为全局最优解中买入的当天的价格，Psell为全局最优解中卖出的当天的价格

那么公式如下

\[Psell - Pbuy = (Psell - p_i) + (p_i - Pbuy) \]

那么就相当于，我们在pi天把Pbuy时的股票卖掉，再以pi的价格买回来，再在Psell时卖掉，也就是说我们买价格最小的股票再以最大的价格卖掉，以达成最优解

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct node {
    int value;
    bool operator < (const node &v) const
    {
        if(value > v.value)return(true);
        else return(false);
    }
}a[330000];
priority_queue<node>q;

ll ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;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.empty() && q.top().value < a[i].value) {//假如当前的股票价格不是最优解
            ans += a[i].value - q.top().value;//将差值计入全局最优解 
            q.pop();//将已经统计的最小的股票价格丢出去
            q.push(a[i]);//反悔策略：将当前的股票价格再放入堆中，即记录中间变量（等式中间的Vi)
        }
    }

    cout << ans;
    return 0;
}

双向链表反悔自动机

这道题的模板题是种树

P1484 种树~~（真的是种树）~~

简要题意：一条直线上有n个坑，你有k个树种用来种树，没种一颗树你都会获得对应的利益，但相邻的两个坑不能种树

考虑反悔自动机，那么要构建差值公式

先举个简单的例子：假如我们有4个坑A, B, C, D，对应的利益为a, b, c, d

假如我们选择了B点，我们能获得的最大利益为b + d（种子一定够用）

但能肯定此时为最优解吗？

不一定，可能选择A和C是最优的

观察发现

\[a + c < b + d\\ a + c - b < d\\ \]

我们新加入一个P点，他对应的价值为a + c - b，并删点A和C点

如果我们下一次选择了P，就证明我们后悔了

假如说我们要操作的点在两端呢？

那么一定不会进行反悔操作，直接删掉即可

如果我决定删除A，就代表A的值是大于B的值的，那我们就没有可能反悔了。这是因为假如我们反悔了选了B不选A，那我们得到的值b小于a，并且影响了C让C不能选了（选A时C是可以选的），可以说是赔了夫人又折兵，所以是不可能反悔的直接把A和B都删了就可以了。

——————摘自蒟蒻大佬

感觉自己说的不太明白，就引用了一下，感谢jvruo大佬！

#include<bits/stdc++.h>
using namespace std;
struct node {
    long long site, val;
    bool operator < (const node &v) const {
        if(v.val > val) return(true);
        else return(false);
    }
}now, x;
long long val[2200000];//价值 
long long vis[2200000], l[2200000], r[2200000];
//vis用于记录是否删除（1为删除），l，r为双向链表的左右邻居 
long long t, n, m;
long long ans;
priority_queue<node>q;
int main()  {
    scanf("%lld%lld", &n, &m);

    for(long long i = 1; i <= n; i++) scanf("%lld", &val[i]);
    while(!q.empty()) q.pop();

    for(long long i = 1; i <= n; i++) {
        now.site = i;
        now.val = val[i];
        vis[i] = 0;
        q.push(now);
    } 

    for(long long i = 2; i <= n; i++) l[i] = i - 1;
    for(long long i = 1; i <= n - 1; i++) r[i] = i + 1;

    l[1] = r[n] = 0;
    //预处理，制作堆和双向链表 

    for(long long i = 1; i <= m; i++) {
        x = q.top(); q.pop();
        while(vis[x.site] == 1) {
            x = q.top();
            q.pop();
        }//找到一个没有被删除的值最大的点 
        if(x.val < 0) break;
        ans +=  x.val;

        if(l[x.site] != 0) vis[l[x.site]] = 1;//删除左边的点 
        if(r[x.site] != 0) vis[r[x.site]] = 1;//删除右边的点 

        if(l[x.site] != 0 && r[x.site] != 0) {
            now.site = x.site;
            now.val = val[l[x.site]] + val[r[x.site]] - val[x.site];
            val[x.site] = val[l[x.site]] + val[r[x.site]] - val[x.site];
            r[l[l[x.site]]] = x.site;
            l[x.site] = l[l[x.site]];
            l[r[r[x.site]]] = x.site;
            r[x.site] = r[r[x.site]];
            q.push(now);
        }//如果不在链表两端 
        else if(l[x.site]) r[l[l[x.site]]] = 0;
        else l[r[r[x.site]]] = 0;   
        //如果在链表两端 
    }

    printf("%lld\n", ans);
    return 0;
}

part.4

总结

在网上看了不少资料，感觉还是jvruo大佬讲的比较详细，他的博客对我的帮助很大，此处对jvruo大佬表示真挚的感谢

感觉对应反悔贪心的知识点仍需要时间去理解

标签：node,return,int,long,反悔,const,KuonjiCat,贪心
From： https://www.cnblogs.com/Kounjicat/p/18566325

KuonjiCat的算法学习笔记：反悔贪心