B1826 [JSOI2010]缓存交换 贪心+离散化+堆
发布日期:2021-08-19 11:09:49 浏览次数:2 分类:技术文章

本文共 1890 字,大约阅读时间需要 6 分钟。

这个题仔细一想可以直接贪心做,因为队列里下一个出现的早的一定最优。正确性显然。然后我只拿了50,我直接模拟另一个队列暴力修改最后一个点的nxt值,自然会T。但是其实不用修改,直接插入就行了前面的不影响后面的。然而只有80分,因为没有离散化。

题干:

Description在计算机中,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缺失次数。Input输入文件第一行包含两个整数N和M(1<=M<=N<=100,000),分别代表了主存访问的次数和Cache的容量。 第二行包含了N个空格分开的正整数,按访问请求先后顺序给出了每个主存块的编号(不超过1,000,000,000)。Output输出一行,为Cache缺失次数的最小值。Sample Input6 21 2 3 1 2 3Sample Output4HINT在第4次缺失时将3号单元换出Cache。SourceJSOI2010第二轮Contest2

代码:

#include
#include
#include
#include
#include
#include
#include
using namespace std;#define duke(i,a,n) for(int i = a;i <= n;i++)#define lv(i,a,n) for(int i = a;i >= n;i--)#define clean(a) memset(a,0,sizeof(a))const int INF = 1 << 30;typedef long long ll;typedef double db;template
void read(T &x){ char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x;}template
void write(T x){ if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10);}struct node{ int nxt,w; bool operator < (const node &oth) const { return nxt < oth.nxt; }} a[200010];int num = 0,n,m,tot,ans = 0;int lst[200010];int vis[200010];int k[200010];priority_queue
qu;int main(){ read(n); read(m);// cout<
<
= m) { node f = qu.top();// cout<
<<" "<
<

 

转载于:https://www.cnblogs.com/DukeLv/p/9752046.html

转载地址:https://blog.csdn.net/weixin_30924087/article/details/96948760 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:FPGA时序约束一点总结
下一篇:oracle外键约束学习

发表评论

最新留言

关注你微信了!
[***.104.42.241]2024年02月29日 07时28分00秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

python问题描述怎么写_python写文件有时候写不进去怎么办 2019-04-21
qpython3安装lxml_在python的lxml中使用xml目录? 2019-04-21
java 幂取模_快速幂取模算法 2019-04-21
java build path jre_java-如何在安装了jre 7后为Jre 6设置路径? 2019-04-21
java上传下载源码_javaweb简单实现文件上传与下载源代码 2019-04-21
java socket udp 广播_1.Java 的屏幕广播(基于UDP),2.多线程下载器 2019-04-21
java控制热敏打印机的例子.rar_stm32控制热敏打印机 2019-04-21
java clone equals_(原)java中对象复制、==、equals 2021-06-24
java滚动字幕实训报告_Java实习报告 (7000字).doc 2021-06-24
php7 memcached.exe,PHP7 下安装 memcache 和 memcached 扩展 2021-06-24
计算机二级java技巧,计算机二级报java难考吗 2021-06-24
php foreach 数据库,php – 使用foreach将数据库检索的数据排列在HTML表中 2019-04-21
拉格朗日matlab编程例题,Matlab习题讲解.doc 2019-04-21
case是不是php语言关键字,PHP语言 switch 的一个注意点 2019-04-21
linux php mkdir失败,linux – mkdir错误:参数无效 2019-04-21
config.php渗透,phpMyAdmin 渗透利用总结 2019-04-21
java list 合并 重复的数据_Java ArrayList合并并删除重复数据3种方法 2019-04-21
android volley 上传图片 和参数,android - 使用android中的volley将图像上传到multipart中的服务器 - 堆栈内存溢出... 2019-04-21
android开发的取消清空按钮,Android开发实现带清空按钮的EditText示例 2019-04-21
android gp服务,ArcGIS Runtime SDK for Android开发之调用GP服务(异步调用) 2019-04-21