如何为网站开发app,计算机软件开发工资高吗,wamp在网站建设中的功能及协作关系,wordpress 主题安装目录文章目录题目描述解析代码题目描述 解析
这题感觉做的不错 不难看出#xff0c;要维护一个空闲的优先队列#xff0c;在每次申请时弹出编号最小的
但是对判断当前哪些被访问的内存重新进入空闲状态是一个难题 最简单的办法是存起来每次扫一遍判断 但这样在极端数据时会TLE要维护一个空闲的优先队列在每次申请时弹出编号最小的
但是对判断当前哪些被访问的内存重新进入空闲状态是一个难题 最简单的办法是存起来每次扫一遍判断 但这样在极端数据时会TLE题解里那个和数据构造者斗智斗勇的写法就邪门 那么怎么办呢
很容易想到也用一个优先队列维护 但问题是在访问时内存到期时间会后延 而优先队列是不支持这一点的 但我们想到 干脆不管原先在占用队列里的那个内存了 直接再往里push一个新的 然后用num数组记录每个内存在占用队列里出现的次数 每次弹出时– 然后当num0时才是空闲的
写但这里本题已经过了 但是我们又发现占用队列其实一定是先进先出的 那还优先个球啊 直接队列就行了 不过由于空闲队列还是优先队列 所以时间复杂度还是nlogn 只是常数小了一点 多少快了点
AC
代码
#includebits/stdc.h
using namespace std;
const int N3e6100;
#define ll long long
int n;
int x,y,t;
char s;
struct node{int id,t;bool operator (const node y)const{return ty.t;}
};
priority_queueint,vectorint,greaterint fre;
queuenodecpu;
int num[N];
int main(){for(int i1;i30000;i) fre.push(i);while(scanf(%d %c,t,s)!EOF){while(!cpu.empty()cpu.front().tt){int ocpu.front().id;cpu.pop();if(--num[o]0) fre.push(o); }
// scanf( %c ,s);
// printf(%c\n,s);if(s){int nowfre.top();fre.pop();printf(%d\n,now);num[now];cpu.push((node){now,t600});}else{scanf(%d,x);if(x30000) printf(-\n);else{if(num[x]){printf(\n);num[x];cpu.push((node){x,t600});}else{printf(-\n);}}}}return 0;
}
/*
1
1
1
2 . 2
2 . 3
3 . 30000
601 . 1
601 . 2
602 . 3
602
602
1202 . 2
*/
