首页 > 编程语言 >【算法学习】反悔贪心

【算法学习】反悔贪心

时间:2024-11-06 21:19:57浏览次数:1  
标签:val int long 反悔 算法 我们 贪心

前言

反悔贪心,先选择局部最优,当不断向后更新时发现前面的决策在现在来看并不优就进行调整过去决策进行局部最优,可以说反悔贪心一步步扩宽自己的视野从而明白过去的错误。、

如果动态规划是将各种削苹果的方式都展示出来的话,那反悔贪心就是削一下补回来一点再削。

当然反悔贪心的题是可以用动态规划做的,但是在有些题数据范围很大或不方便转移时就可以考虑反悔贪心。

反悔堆

用堆维护最差的决策,之后有更优的决策可以快速掉替换这个决策。

P2949 Work Scheduling G

因为有个截至时间,所以我们贪心地想截至时间越晚的我们越靠后考虑,当然我们也想让价值更大,所以我们按照截至时间从小到大排序,其次按照权值排序。

然后我们用小根堆维护选择的数,如果我们新加的数的截至时间为堆内元素个数,那么我们就要看看能不能删掉数,我们查看堆顶元素是否小于新加的元素,如果小于我们就删掉堆顶让当前元素入堆,我们不断地进行贪心与策略调整。

远古时期的代码,和我讲的有一点点点区别。

#include <bits/stdc++.h>
using namespace std;
int n;
long long ans=0;
struct ss{
	int t,p;
}a[100005];

bool cmp(ss g,ss h){
	return g.t<h.t;
}

priority_queue<int,vector<int>,greater<int> >q;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    	scanf("%d%d",&a[i].t,&a[i].p);
	}
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
    	if(a[i].t<=q.size()){
    		if(q.top()<a[i].p){
				ans-=q.top();
				q.pop();
				q.push(a[i].p);
				ans+=a[i].p; 
			} 
		}
		else{
			ans+=a[i].p;
    		q.push(a[i].p);
		}
	}
    cout<<ans;
    return 0;
}

P4053 [JSOI2007] 建筑抢修

通过不断调整使得花费总时间尽量少,改一改上面那题的条件与不断调整 \(sum\) 值。

反悔自动机

通过特殊的策略使得总是维护最优策略,通常应用到有特殊限制的题目上,例如 \(A\) 和 \(B\) 两者选 \(1\),\(C\) 和 \(D\) 两者选 \(1\),假设我们已选 \(A,C\),我们想选 \(B\) 的话就要加上 \(B-A\) 使得自动反悔 \(A\) 从而维护最优策略。

Buy Low Sell High

我们考虑我们答案形式并进行转变为 \(C_{sell}-C_{buy}\) 我们通过售价减购价的形式,我们考虑引入一个反悔物使得我们每当销售例如 \(C_i-C_j\) 就会产生这个反悔物 \(val\),当我们之后选择这个反悔物时就可以更新为新的获利 \(C_i-C_k\),于是我们有以下方程 \(C_i-C_j+C_k-val=C_i-C_k\),最后可知 \(C_j=val\),所以我们用小根堆维护最小的数,如果最小的数一个新的数那也就是产生新的组合,总的加多少减多少是不变的,反正不亏,如果最小的数是反悔物那么我们也进行反悔策略,调整变得更大,反正不亏。

#include <bits/stdc++.h>
#define int long long
#define re register
using namespace std;
int n;
int ans;
priority_queue<int,vector<int>,greater<int> > q;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++){
    	int x;
    	cin>>x;
    	if(!q.empty()&&q.top()<x){
    		ans+=x-q.top();
    		q.pop();
    		q.push(x);
		}
		q.push(x);
	}
	cout<<ans;
	return 0;
}

标签:val,int,long,反悔,算法,我们,贪心
From: https://www.cnblogs.com/sadlin/p/18531055

相关文章

  • C语言数据结构--详细讲解算法复杂度
    C语言数据结构-算法复杂度前言一、时间复杂度1.大O渐进表示法2时间复杂度的计算二、空间复杂度1.什么是空间复杂度2时间复杂度的计算总结前言我们都清楚计算机存储和组织数据是通过数据结构来实现的。当计算机对这些数据结构中的数据进行遍历等操作时,这个过程就......
  • 代码随想录算法训练营第十八天|leetcode530.二叉搜索树的最小绝对差、leetcode501.二
    1leetcode530.二叉搜索树的最小绝对差题目链接:530.二叉搜索树的最小绝对差-力扣(LeetCode)文章链接:代码随想录视频链接:你对二叉搜索树了解的还不够!|LeetCode:98.验证二叉搜索树_哔哩哔哩_bilibili思路:定义一个极大值作为结果,然后在中序遍历过程中进行比较出结果1.1自己的......
  • 算法笔记——马拉核弹(Mana Nuclear)
    0x00摘要“马拉核弹”算法由SXHT同学(2009~今)发明,并在2024年11月于某不知名学校机房内正式公布。该算法基于1975年发明的Manacher算法,并将其推广至对称正方形问题。原文链接与密码:sunxuhetai2009。关键词:Manacher算法信息学对称正方形0x01缘由先来看这道题目:......
  • Python——数据结构与算法-时间复杂度&空间复杂度-链表&树状结构
    1.数据结构和算法简介程序可以理解为:程序=数据结构+算法概述/目的:都可以提高程序的效率(性能)数据结构指的是存储,组织数据的方式.算法指的是为了解决实际业务问题而思考思路和方法,就叫:算法.2.算法的5大特性介绍概述:为了解决实际业务问题,......
  • 基于GA-PSO-SVM算法的混沌背景下微弱信号检测matlab仿真
    1.算法运行效果图预览(完整程序运行后无水印) svm参数取值对检测性能的影响: SVM,PSO,GA-PSO-SVM的检测性能对比: 2.算法运行软件版本matlab2022a 3.部分核心程序(完整版代码包含详细中文注释和操作步骤视频,参考文献,说明文档)loadGAPSO.mat%调用四个最优的......
  • 经典算法思想总结
    在计算机科学的世界里,算法是解决问题的核心工具。它们不仅定义了如何解决问题,还决定了解决问题的效率。以下是一些经典算法思想的总结,这些思想跨越了多个领域,从数据结构到机器学习,都是构建高效算法的基石。1.分治法(DivideandConquer)分治法是一种将问题分解成更小的子问......
  • C++算法相关一些小细节
    C++算法相关一些小细节cin>>stl;//输入字符串时,遇到空格或者回车就会停止cout<<stl<<endl;//输出字符串时,遇到空格或者回车不会停止若要往字符数组读入一行字符串,包括空格,那么就要写成           String类1. 2.3.不能用printf直接......
  • 极端天气下的目标检测与单目测距算法(毕业设计附代码)
    代码获取:代码本文主要工作:科技的发展与进步促使自动驾驶车辆逐渐成为全球汽车产业发展的重要战略方向。但自动驾驶车辆面对如:大雨、大雾、大雪等极端环境时,智能汽车图像采集与处理系统将面临巨大挑战。并且自动驾驶需要实时关注周围物体的威胁,实时进行目标检测以及精确......
  • 回溯算法
    一、什么是回溯算法回溯算法是一种经典的递归算法,通常用于解决组合问题、排列问题和搜索问题等。回溯算法的基本思想:从一个初始状态开始,按照一定的规则向前搜索,当搜索到某个状态无法前进时,回退到前一个状态,再按照其他的规则搜索。回溯算法在搜索过程中维护一个状态树,通过遍......
  • P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G:贪心
    [NOIP2004提高组]合并果子/[USACO06NOV]FenceRepairG题目描述在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的......