《算法竞赛进阶指南》内存分配

Noi1999 内存分配

内存是计算机重要的资源之一，程序运行的过程中必须对内存进行分配。经典的内存分配过程是这样进行的：

1. 内存以内存单元为基本单位，每个内存单元用一个固定的整数作为标识，称为地址。地址从0开始连续排列，地址相邻的内存单元被认为是逻辑上连续的。我们把从地址i开始的s个连续的内存单元称为首地址为i长度为s的地址片。

2. 运行过程中有若干进程需要占用内存，对于每个进程有一个申请时刻T，需要内存单元数M及运行时间P。在运行时间P内（即T时刻开始，T+P时刻结束），这M个被占用的内存单元不能再被其他进程使用。

   3、假设在T时刻有一个进程申请M个单元，且运行时间为P，则：

1. 若T时刻内存中存在长度为M的空闲地址片，则系统将这M个空闲单元分配给该进程。若存在多个长度为M个空闲地址片，则系统将首地址最小的那个空闲地址片分配给该进程。

2. 如果T时刻不存在长度为M的空闲地址片，则该进程被放入一个等待队列。对于处于等待队列队头的进程，只要在任一时刻，存在长度为M的空闲地址片，系统马上将该进程取出队列，并为它分配内存单元。注意，在进行内存分配处理过程中，处于等待队列队头的进程的处理优先级最高，队列中的其它进程不能先于队头进程被处理。

现在给出一系列描述进程的数据，请编写一程序模拟系统分配内存的过程。

Input

第一行是一个数N，表示总内存单元数（即地址范围从0到N-1）。从第二行开始每行描述一个进程的三个整数T、M、P（M <= N）。最后一行用三个0表示结束。
数据已按T从小到大排序。
输入文件最多10000行，且所有数据都小于109。
输入文件中同一行相邻两项之间用一个或多个空格隔开。

Output
包括2行。
第一行是全部进程都运行完毕的时刻。
第二行是被放入过等待队列的进程总数.

Sample Input
10
1 3 10
2 4 3
3 4 4
4 1 4
5 3 4
0 0 0

Sample Output
12
2

/*
    从数组暴力模拟内存空间的MLE 
    到使用链表将空间直接分块合并的TLE
    再到使用考虑时间的优化 因为找时间少了‘=’华丽wa掉  
*/
#include<iostream>
#include<cmath>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
#define debug cout<<"bug"<<endl 
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=f;
} 
struct node{   //node在两个等待和进行队列中不断判断 
    int t,m,p;
}e;
queue<node>now;
queue<node>wait;
int n,ans;
struct mem{    //为内存空间 以链表存储可无关大小 
    int big,over,nxt;
}v[400100]; 
int cnt=1,minx;
int find(node a,int begin)
{
    int flag=0;
    minx=199999999;
    for(int i=1;i;i=v[i].nxt)//单链表储存空间 
    {
        //为便于统计 合并为后一个向前一个  分配为前一个向后一个[使用前一个，后一个留空] 
        while(v[i].nxt!=0 && v[i].over<begin &&v[v[i].nxt].over<begin)//合并 
        {
//            cout<<"合并"<<begin<<" "<<a.t <<" "<<endl; 
            v[i].big = v[i].big +v[v[i].nxt].big ;
            v[i].over = max(v[i].over ,v[v[i].nxt ].over );
            v[i].nxt =v[v[i].nxt].nxt ;
        }
        if(!flag && v[i].over <begin && v[i].big >= a.m)//分配 时间&&空间
        {
//            cout<<"分配"<<begin<<" "<<a.t <<" "<<endl;
            flag=1;
            if(v[i].big == a.m) v[i].over = begin+a.p-1;//便于操作 不将以适合的空间分出0来 
            else
            {
                cnt++;
                v[cnt].nxt = v[i].nxt ;
                v[i].nxt =cnt;
                v[cnt].over = v[i].over;
                v[i].over = begin+a.p-1;
                v[cnt].big =  v[i].big - a.m;
                v[i].big = a.m;
            }
        }
        if(v[i].over >=begin && v[i].over <minx) minx=v[i].over ;//优化处理时间 （就是这个等号！！！！） 
    }   // 最早结束时间 要求大于等于现在  
    return flag;
}
int main()
{
    read(n);
    read(e.t),read(e.m),read(e.p);
    v[1].big =n,v[1].over =-1;
    while(e.t!=0 || e.m!=0 || e.p!=0)
    {
        now.push(e);  //先将所有的数据push进入 进行队列 
        read(e.t),read(e.m),read(e.p);
    }
    int i=now.front().t; //时间优化方式 以等待队列开头与结束时间的最小值跳转 
    int aad;             //特殊处理：如果当轮未进行任何分配操作 则时间++ 
    while(!now.empty() || !wait.empty() )
    {
        aad=0;               //两个队列进行模拟 注意：等待队列开头的优先级大于进行队列 
        while(!wait.empty()) //并且同轮可进行多次操作 优先级同上 
        {
            if(find(wait.front(),i)) aad++,wait.pop();
            else break;
        }
        while(!now.empty() && now.front().t<=i )
        {
            if(!find(now.front(),i)) aad--,ans++,wait.push(now.front());
            aad++;           //不论如何++ 如果没有进行在上一行会-- 因此只记录了成功次数 
            now.pop();
        }
        if(!aad) i++;//cout<<"1"<<endl;    //本轮的时间对于任何队列均不成立 
        else if(!now.empty()) i=min(minx+1,now.front().t); //now队列还存在值 
        else if(minx!=199999999) i=minx+1;   //now为空 且minx改变过 
    }                             //min记录的结束时间因该从他的下一秒开始（当然从他开始会进入++ 更耗费时间） 
    while(v[1].nxt!=0)//合并 （确保只留下一整个空间块） 
    {
//        cout<<"合并"<<endl; 
        v[1].big = v[1].big +v[v[1].nxt].big ;
        v[1].over = max(v[1].over ,v[v[1].nxt ].over );
        v[1].nxt =v[v[1].nxt].nxt ;
    }
    printf("%d\n%d",v[1].over+1,ans);
    return 0;
}