【BZOJ1826】【洛谷P4404】缓存交换【贪心】【堆】_stoorz1023的博客-程序员秘密

技术标签:   贪心  随机挑战Part4  

题目大意:

题目链接:
BZOJ:https://www.lydsy.com/JudgeOnline/problem.php?id=1826
洛谷:https://www.luogu.org/problemnew/show/P4404

在计算机中,CPU只能和高速缓存Cache直接交换数据。当所需的内存单元不在Cache中时,则需要从主存里把数据调入Cache。此时,如果Cache容量已满,则必须先从中删除一个。 例如,当前Cache容量为3,且已经有编号为10和20的主存单元。 此时,CPU访问编号为10的主存单元,Cache命中。 接着,CPU访问编号为21的主存单元,那么只需将该主存单元移入Cache中,造成一次缺失(Cache Miss)。 接着,CPU访问编号为31的主存单元,则必须从Cache中换出一块,才能将编号为31的主存单元移入Cache,假设我们移出了编号为10的主存单元。 接着,CPU再次访问编号为10的主存单元,则又引起了一次缺失。我们看到,如果在上一次删除时,删除其他的单元,则可以避免本次访问的缺失。 在现代计算机中,往往采用LRU(最近最少使用)的算法来进行Cache调度——可是,从上一个例子就能看出,这并不是最优的算法。 对于一个固定容量的空Cache和连续的若干主存访问请求,聪聪想知道如何在每次Cache缺失时换出正确的主存单元,以达到最少的Cache缺失次数。


思路:

首先,当Cache满了之后,选择已有单元中下一次出现位置最后的删除是最优秀的。因为删除的位置越后,中间可以避免其他的缺失个数就越多,相对的缺失次数就会越少。
维护 n e x t [ x ] next[x] next[x]表示下一个和元素 a [ x ] a[x] a[x]相同的元素位置。这个是可以 O ( n ) O(n) O(n)求出来的。
然后我们要维护多个二元组 ( x , i ) (x,i) (x,i),其中 i i i表示选择第 i i i个位置的元素, x x x表示 n e x t [ i ] next[i] next[i]。我们要在选择的不超过 m m m个二元组中选择 x x x尽量大的删除。所以可以用优先队列来维护。
注意到若两个元素 x , y x,y x,y相同,设 x x x的位置在 y y y后面( x x x入队时间比 y y y晚),那么必然有 n e x t [ x ] > n e x t [ y ] next[x]>next[y] next[x]>next[y]。所以其实可以不用删除前面的 y y y,因为 x x x必然可以覆盖掉 y y y,在 y y y的前面出队。
时间复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn)


代码:

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define mp make_pair
using namespace std;

const int N=100010;
int n,m,tot,ans,sum,a[N],b[N],last[N],next[N];
priority_queue<pair<int,int> > q;
bool inque[N];

int main()
{
    
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
    
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	tot=unique(b+1,b+1+n)-b-1;
	for (int i=1;i<=n;i++)
		a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
	memset(last,0x3f3f3f3f,sizeof(last));
	for (int i=n;i>=1;i--)
	{
    
		next[i]=last[a[i]];
		last[a[i]]=i;
	}
	for (int i=1;i<=n;i++)
	{
    
		if (ans<m && !inque[a[i]])
		{
    
			ans++;
			inque[a[i]]=1;
		}
		else if (ans>=m && !inque[a[i]])
		{
    
			ans++;
			inque[a[i]]=1;
			inque[q.top().second]=0;
			q.pop();
		}
		q.push(mp(next[i],a[i]));
	}
	printf("%d\n",ans);
	return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/SSL_ZYC/article/details/95098951

智能推荐

(AAAI-2019)STA:用于大规模基于视频的行人重识别的时空注意力_顾道长生'的博客-程序员秘密_sta模型

STA:用于大规模基于视频的行人重识别的时空注意力paper题目:STA: Spatial-Temporal Attention for Large-Scale Video-Based Person Re-Identificationpaper是贝克曼研究所发表在AAAI-2019的工作paper地址:链接Abstract这项工作提出了一种新颖的时空注意力 (STA) 方法来解决视频中的大规模行人重识别任务。与大多数现有的方法不同,这些方法简单地使用帧级聚合(例如平均池化)来计算视频剪

【算法笔记】递归树应用实例:计算归并排序平均时间复杂度__gamer的博客-程序员秘密

递归树递归树是迭代的图形表示,可用于求解递推方程。例1:利用递归树计算归并排序的平均时间复杂度。归并排序伪代码:MergeSort(A,p,r){ if(p&amp;amp;amp;lt;r) { q = (p+r)/2; MergeSort(A,p,q); MergeSort(A,q+1,r); Merge(A,p,q,r); //合并两个子数组 } }根据以上的伪代码,可以写...

深入浅出Linux内核内存管理基础_Smith先生的博客-程序员秘密_内核内存管理

1 背景知识1.1 用户空间与内核空间内存的划分       从Linux操作系统层次上,内存可划分为用户空间内存和内核空间内存。       32位的CPU,最大寻址范围为2^32 - 1也就是4G的线性地址空间。Linux简化了分段机制,使得虚拟地址与线性地址总是一致的。Linux一般把这个4G的地址空间划分为两个部分:其中 0~3G为用户程序地址空间,虚地址0x00000000到

数据库的分页查询---by wjf(2020.5.17)_A-Jeffrey的博客-程序员秘密

在我们实际的项目开发之后,数据库里的数据很有可能是成千上万的,那我们肯定不可能一下子就把全部的数据都取出来,这样子电脑可能会受不了,所以这时候就需要用到数据库的分页查询了。分页查询逻辑图如下:首先第一步我们先编写pager实体类package cn.edu.mju.project1.util;import java.util.List;//首先写辅助类public class Pager { private int page = 1; //当前页号 private int

I2C详细介绍_marc07的博客-程序员秘密

(资料参考来源于百度)IIC即Inter-Integrated Circuit(集成电路总线),这种总线类型是由飞利浦半导体公司在八十年代初设计出来的,主要是用来连接整体电路(ICS),IIC是一种多向控制总线,也就是说多个芯片可以连接到同一总线结构下,同时每个芯片都可以作为实时数据传输的控制源。这种方式简化了信号传输总线接口。I2C串行总线一般有两根信号线,一根是双向的数据线SD

[iOS]Objective-C编程规范_流火緋瞳的博客-程序员秘密

介绍这是一份编程规范,主要参考了raywenderlich、github和苹果官方的Objective-C编程规范。相关文档链接在文末给出。背景知识这里是一些苹果官方描述oc编码规范的文档,如果有些规范这里没有提到,请参照这些文档:The Objective-C Programming LanguageCocoa Fundamentals GuideCodi

随便推点

20162309《程序设计与数据结构》第二学期课程总结_aoyi8281的博客-程序员秘密

每周作业链接汇总1.http://www.cnblogs.com/Metwox/p/7501901.html第一周作业,简要内容:学习基本的算法分析,了解算法复杂度的基本内容。2.http://www.cnblogs.com/Metwox/p/7536289.html第二周作业,简要内容:教材第13章内容,学习排序和查找,了解几种查找方式的区别和联系。3.http://www.cn...

wordpress博客插件_WordPress插件来管理多授权博客_cune1359的博客-程序员秘密

内容为准,让共同作者/ 特约作者在您的博客上发布内容是增加博客数量(和质量)的最简单方法。 但是,管理多个作者不是一件容易的事-尤其是当他们是新手并且不熟悉您博客的原理时。 幸运的是,有许多WordPress插件可以帮助您处理多位作者及其作品。 这是一些最好的WordPress插件列表,可以简化作者的管理。 请注意,以下给出的所有插件在WordPress 3.0版本之前都具有最低兼容性。 ...

malloc/free VS new/delete_lanzily99的博客-程序员秘密

1.malloc和new  malloc与free是C++/C语言的标准库函数,new/delete是C++的运算符,它们都可用于申请动态内存和释放内存。对于非内部数据类型的对象而言,光用maloc/free无法满足动态对象的要求。对象在创建的同时要自动执行构造函数,对象在消亡之前要自动执行析构函数,由于malloc/free是库函数而不是运算符,不在编译器控制权限之内,不能够把执行构造函

Bootstrap 模态框(Modal)带参数传值实例_潇潇雨歇_的博客-程序员秘密_bootstrap模态框传值

模态框(Modal)是覆盖在父窗体上的子窗体。通常,目的是显示来自一个单独的源的内容,可以在不离开父窗体的情况下有一些互动。子窗体可提供信息、交互等。    为了实现父窗体与其的交互,通常需要向其传值,实现带参数的传递,查看数据的唯一性。例如下面窗体:    为了实现其回复的唯一性和带参传值的功能,需要做以下处理

gcc:预处理语句--#include和#include_next_wuzuyu365的博客-程序员秘密

gcc:预处理语句--#include和#include_next分类: C/C++ 2010-01-23 09:23 3915人阅读 评论(2)收藏 举报gcc文档工作unixc编程       原创文章,转载请注明出处,谢谢!               作者:清林,博客名:飞空静渡 #include如果从纯粹的text文件来说,#i

Redis List问题_sinat_27016095的博客-程序员秘密

在&nbsp;C&nbsp;语言中,字符串采用的是一个&nbsp;char&nbsp;数组(柔性数组)来存储字符串,而且字符串必须要以一个空字符串&nbsp;\0&nbsp;来结尾。而且字符串并不记录长度,所以如果想要获取一个字符串的长度就必须遍历整个字符串,直到遇到第一个&nbsp;\0&nbsp;为止(\0&nbsp;不会计入字符串长度),故而获取字符串长度的时间复杂度为&nbsp;O(n)。正因为&nbsp;C&nbsp;语言中是以遇到的第一个空字符&nbsp;\0&nbsp;来识别是否到了字符串末

推荐文章

热门文章

相关标签