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

反悔贪心学习笔记

时间:2024-06-09 17:33:32浏览次数:27  
标签:int ll t2 笔记 反悔 最优 贪心

算法:

反悔贪心,顾名思义就是贪心的时候 反悔

意思是:如果这一步的贪心 不是全局最优解,就退回去一步,换一种贪心策略。

一般分为 反悔自动机反悔堆

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

反悔堆则是:通过 来维护当前贪心策略的最优解,若发现最优解不对,就 退回上一步,更新最优解。

题目:

模板题:P4053 建筑抢修

link

首先我们将 \(t2\) 从小到大排序。

然后用大根堆维护每一个元素。

在贪心的过程中,若发现目前不是最优解,那么就取堆顶元素,来保证正确性。

代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+10;
ll n,ans,s;
priority_queue<ll> q;
struct P{
	ll t1,t2;
}a[N];
bool cmp(P l,P r){
	return l.t2<r.t2;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].t1>>a[i].t2;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		s+=a[i].t1,q.push(a[i].t1);
		if(s<=a[i].t2) ans++;
		else s-=q.top(),q.pop();
	}
	cout<<ans;
	return 0;
}

标签:int,ll,t2,笔记,反悔,最优,贪心
From: https://www.cnblogs.com/jianhe/p/-/repent_greedy

相关文章

  • Java Web学习笔记29——Vue路由
    Vue路由:前端路由:点击菜单栏,地址栏会发生变化,会显示对应的组件。URL中的Hash(#号后面的部分)与组件之间的对应关系。Hash是/dept,那么就是部门管理组件;Hash是/emp,那么就是员工管理组件;VueRouter:介绍:VueRouter是Vue的官方路由;组成:1)VueRouter:路由器类,根据路由请求在路......
  • 计算机网络个人笔记
    ARP过程简易叙述想要与对端主机通信首先查看本地高速缓存表中是否有到对端主机的地址,如果本地缓存未老化或者自清除,有则直接让网关转发;没有地址则开始进行ARP广播向网关请求已知通信IP地址的Mac地址。网关收到ARP请求地址查询本地路由表为其进行下一步,如果本地路由表没有查到请......
  • RabbitMQ笔记
     端午无聊,就来学学MQ吧消息队列消息指的是两个应用之间传递的数据消息队列是在消息传递中保存消息的容器生成者:只负责发送数据消费者:只负责读取数据(数据就是消息)为什么要用消息队列解耦如果一个系统(系统a)的需求是共享自己系统的数据,而其他系统(系统BCD)是需求者。而......
  • Objective-C 学习笔记 | 基础
    Objective-C学习笔记|基础参考书:《Objective-C编程(第2版)》第1部分入门Objective-C语言是以C语言为基础的,但增加了对面向对象编程的支持。Objective-C语言是用来开发在苹果iOS以及OSX操作系统上运行的应用的编程语言。第2部分如何编程该部分讲解了C语言编程的必......
  • CUDA编程学习笔记-02
    CUDA代码高效计算策略高效公式✒️Math代表数学计算量,Memory代表每个线程的内存......
  • FFmpeg开发笔记(二十八)Linux环境给FFmpeg集成libxvid
    ​XviD是个开源的视频编解码器,它与DivX一同被纳入MPEG-4规范第二部分的视频标准,但DivX并未开源。早期的MP4视频大多采用XviD或者DivX编码,当时的视频格式被称作MPEG-4。现在常见的H.264后来才增补到MPEG-4规范的第十部分,当然如今使用XviD压缩的视频已经不多了。在《FFmpeg开发实战......
  • OpenCompass大模型测评实战学习笔记
    一、OpenCompass介绍:评测相关:评测意义:研究评测对于我们全面了解大型语言模型的优势和限制至关重要;研究评测有助于指导和改进人类与大型语言模型之间的协同交互;研究评测可以帮助我们更好地规划大型语言模型未来的发展;评测能了解不同语言模型之间的性能、舒适性和安全性,能够帮......
  • 算法课程笔记——可撤销并查集
    算法课程笔记——可撤销并查集Gv......
  • 读AI未来进行式笔记07量子计算
    1.      AI审讯技术1.1.        发明者最初的目的是发明一种能够替代精神药物,为人类带来终极快乐的技术1.1.1.          遗憾的是,他找到的只是通往反方向的大门1.2.        通过非侵入式的神经电磁干扰大脑边缘系统,诱发受审者最为恐惧及......
  • 数据结构学习笔记-堆排序
    堆排序算法的设计与分析问题描述:设计并分析堆排序【前置知识:什么是堆?】堆(Heap)是一种特殊的树形数据结构,它满足以下两个条件之一:最大堆(MaxHeap):每个节点的值都大于或等于其子节点的值。换句话说,根节点的值是整个堆中最大的。最小堆(MinHeap):每个节点的值都小于或等于其......