题解 P5763 【[NOI1999]内存分配】

乐哥 · 2020-02-04 11:21:25 · 题解

队列+堆+链表（用set实现）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int MAXN=10005;
queue<PII> wait; //内存长度，占用时间
set<PII> run; //起始下标，内存长度
priority_queue<PII,vector<PII>,greater<PII> > q; //结束时间，起始下标
int ans,cnt;
bool check(int t,int m,int p) //检查可否插入新进程
{
    set<PII>::iterator it;
    for(it=run.begin();it!=run.end();it++)
    {
        set<PII>::iterator jt=it; jt++;
        if(jt!=run.end())
        {
            int st=it->first+it->second;
            if(jt->first-st>=m)
            {
                run.insert(make_pair(st,m));
                q.push(make_pair(t+p,st));
                return true;
            }
        }
    }
    return false;
}
void free(int t) //释放到t时间为止已结束的进程
{
    while(q.size()&&q.top().first<=t)
    {
        int f=q.top().first;
        while(q.size()&&q.top().first==f)
        {
            PII top=q.top();
            q.pop();
            set<PII>::iterator it=run.lower_bound(make_pair(top.second,0));
            run.erase(it);
        }
        ans=f;
        while(wait.size())
        {
            PII ft=wait.front();
            if(check(f,ft.first,ft.second))
                wait.pop();
            else break;
        }
    }
}
int main()
{
    int n,t,m,p;
    scanf("%d",&n);
    run.insert(make_pair(-1,1));
    run.insert(make_pair(n,1));
    while(scanf("%d%d%d",&t,&m,&p)&&(t||m||p))
    {
        free(t);
        if(!check(t,m,p))
            wait.push(make_pair(m,p)),cnt++;
    }
    free(2e9);
    printf("%d\n%d",ans,cnt);
    return 0;
}