P5763 [NOI1999] 内存分配
P5763 [NOI1999] 内存分配题解
题面
link
思路
非常好模拟，这使我调了一下午。
操作的有序化
首先，对于每个进程有两个操作关于其，插入和删除。
所以我们可以想到实时记录两个操作的执行时间（实时是因为进入等待队列的进程需要重新计算删除时间）。
剩余的工作就交给优先队列了。
需要注意的是，尝试插入等待队列里的进程时，需要先完成当前时刻所有的删除操作，同时，应先处理等待队列的进程，然后再处理新进程，所以应在按时间排序的基础上，将删除操作提前。让已完成的进程让出空间再处理。
代码如下：
struct node{
int num,t,opt;//num:进程编号,t:执行时间,opt:操作类型，1为插入，2为删除
friend bool operator<(node a,node b){return (a.t==b.t?a.opt<b.opt:a.t>b.t);}
};while(!q.empty()){
st:
node now=q.top();
q.pop();
ans1=max(ans1,now.t);//记录时间
if(now.opt==1) ins(now.num);
else del(now.num);
if(!q.empty()&&q.top().t==now.t&&q.top().opt==2) goto st;//如果当前时刻仍有删除操作就回去。
wating_ins(now.t);//处理等待队列
}空间分配
注意到题目中空间上限为
代码中定义了头尾两个链表以方便操作。
struct List{int l,r,pre,nxt;}now_using[10005];now_using[1]={-1,-1,-1,2,0},now_using[2]={n,n,1,-1,0};接下来，就剩下几个操作了。
1. 寻找是否有满足条件的空间
从表头开始遍历链表计算两个进程中间剩余的空间，判断能否放入。
int find(int mr){
int now=1;
while(now_using[now].nxt!=-1){
if(now_using[now_using[now].nxt].l-now_using[now].r-1>=mr) return now;
now=now_using[now].nxt;
}
return -1;
}2. 插入
用 find 函数查询是否能插入，如果能，则用正常链表操作，否则加入等待队列。
void ins(int num){
int pos=find(program[num].mr);
if(pos==-1){
wating.push(num);
ans2++;
}else{
int st=now_using[pos].r+1;
cnt++;
now_using[cnt]={st,st+program[num].mr-1,-1,-1};
now_using[cnt].pre=pos,now_using[cnt].nxt=now_using[pos].nxt;
now_using[now_using[pos].nxt].pre=cnt,now_using[pos].nxt=cnt;
to[num]=cnt,q.push({num,program[num].mal+program[num].ti,2});
//注意这里操作类型为2。to是一个映射,在删除时有用。
}
}3. 删除
正常删除即可。
void del(int num){
int now_del=to[num];
now_using[now_using[now_del].pre].nxt=now_using[now_del].nxt;
now_using[now_using[now_del].nxt].pre=now_using[now_del].pre;
}4. 处理等待队列
跟插入差不多，也是先判再插入，注意重新计算时间。
void wating_ins(int now_time){
while(!wating.empty()){
int now=wating.front(),pos=find(program[now].mr);
if(pos!=-1){
int st=now_using[pos].r+1;
cnt++;
now_using[cnt]={st,st+program[now].mr-1,-1,-1};
now_using[cnt].pre=pos,now_using[cnt].nxt=now_using[pos].nxt;
now_using[pos].nxt=now_using[now_using[cnt].nxt].pre=cnt;
to[now]=cnt,q.push({now,now_time+program[now].ti,2});
wating.pop();
}else break;
}
}合起来就是本题的代码了。
code
#include<bits/stdc++.h>
using namespace std;
int n,program_num,ans1,ans2,cnt=2,to[10005];
struct List{int l,r,pre,nxt;}now_using[10005];
struct wating_program{int mal,ti,mr;}program[10005];
struct node{
int num,t,opt;
friend bool operator<(node a,node b){return (a.t==b.t?a.opt<b.opt:a.t>b.t);}
};
queue<int>wating;
priority_queue<node>q;
int find(int mr){
int now=1;
while(now_using[now].nxt!=-1){
if(now_using[now_using[now].nxt].l-now_using[now].r-1>=mr) return now;
now=now_using[now].nxt;
}
return -1;
}
void ins(int num){
int pos=find(program[num].mr);
if(pos==-1){
wating.push(num);
ans2++;
}else{
int st=now_using[pos].r+1;
cnt++;
now_using[cnt]={st,st+program[num].mr-1,-1,-1};
now_using[cnt].pre=pos,now_using[cnt].nxt=now_using[pos].nxt;
now_using[now_using[pos].nxt].pre=cnt,now_using[pos].nxt=cnt;
to[num]=cnt,q.push({num,program[num].mal+program[num].ti,2});
}
}
void del(int num){
int now_del=to[num];
now_using[now_using[now_del].pre].nxt=now_using[now_del].nxt;
now_using[now_using[now_del].nxt].pre=now_using[now_del].pre;
}
void wating_ins(int now_time){
while(!wating.empty()){
int now=wating.front(),pos=find(program[now].mr);
if(pos!=-1){
int st=now_using[pos].r+1;
cnt++;
now_using[cnt]={st,st+program[now].mr-1,-1,-1};
now_using[cnt].pre=pos,now_using[cnt].nxt=now_using[pos].nxt;
now_using[pos].nxt=now_using[now_using[cnt].nxt].pre=cnt;
to[now]=cnt,q.push({now,now_time+program[now].ti,2});
wating.pop();
}else break;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
now_using[1]={-1,-1,-1,2,0},now_using[2]={n,n,1,-1,0};
program_num=1;
while(cin>>program[program_num].mal>>program[program_num].mr>>program[program_num].ti&&program[program_num].mr){
q.push({program_num,program[program_num].mal,1});
program_num++;
}
while(!q.empty()){
st:
node now=q.top();
q.pop();
ans1=max(ans1,now.t);
if(now.opt==1) ins(now.num);
else del(now.num);
if(!q.empty()&&q.top().t==now.t&&q.top().opt==2) goto st;
wating_ins(now.t);
}
cout<<ans1<<"\n"<<ans2;
}