数据结构：堆
题目
请你写一个内存管理系统。 内存中有30000个块，编号为1..30000。 当操作系统需要内存时内存管理系统会找出编号最小的空闲块，向里面写入数据。 操作系统还会会发出指令读取某个编号的内存块。如果目标块空闲，读取失败，否则读取成功。 一开始所有块都是空闲块。被写入数据之后就不是空闲块了。 如果一个块在600秒内没有被写入或读取，这块内存自动清空，变为空闲块。 本题中不会出现内存块不够用的情况。
输入格式
每行一个要求，可能是申请内存或读取。
申请内存的格式如下： T + T表示这条请求收到时的时间，是不大于65000的整数，以秒为单位。
读取内存的格式如下： T . N T表示这条请求收到时的时间，N表示需要读取的内存块的编号(1-30000)。 操作系统的请求不会超过80000个。
请求按照时间增序排序。
输出格式
每行回答一个请求。 对于申请内存的请求，回答一个整数-你分配给它的内存块的编号。 对于读取内存的请求，如果成功输出+，失败输出-。
思路：这题的先后逻辑关系还是要搞清楚的，否则容易错。
1.我们开辟两个堆，一个是空闲堆，一个占用堆，两个都是小顶堆。
2.空闲堆的关键字就是内存单元的编号,这样查找编号最小的空闲单元就是O(1)，维护堆是O(logn)
3.占用堆每个元素需要记录两个元素，一个是内存单元的编号一个是回收该单元的时间，关键字是回收时间
4.另外我们开辟一个数组time,记录每个内存单元的回收时间，如果i单元是空闲的那么time[i]=-1
5.另外内存的回收时间是不断变化的，当一个内存还被占用时读取了它，会重新计时，从那时起再加600才是它的回收时间，所以在占用堆中的元素一旦被读取就要改变回收时间，那么
其在堆中的时间就要改变，要调整，其实就是在元素为根的子树内调整（因为可知一旦重新计时回收时间一定是大于或与原来的时间，该元素应该沿子树方向下滑）。为了知道占用堆中每个元素具体在堆中的什么位置，需要一个数组来记录pos,pos[i]=m,表示i号内存在堆中的第m个下标里存放。因此查询一个内存是否能访问，为O(1)，访问后要调整为O(logn)
6.到达了回收时间，占用堆中过期的元素就要被回收到空闲堆，所以在占用堆中涉及了删除头节点的操作。那什么时候删除过期元素呢？就是读入每条指令的时间后，不管读入的是什么操作，都要先清除掉过期的元素——例如申请内存操作，要先把过期单元放回去申请，例如查询操作，要先清除过期元素才能判断该元素是否还被占用
7.在空闲堆中涉及删除和插入操作所以写了两个函数 insertheap(),delheap()
8.在占用堆中涉及删除，插入和调整操作，但是删除和调整函数可以合并为一个，另外删除相当于在根开始调整，而调整是在其子树上开始调整，因而合并为updata(),另外的是insetHeap()
9.在占用堆中的操作，无论是什么操作，都要记得维护pos数组，不要丢失了它的记录信息
代码有点长，其实重写了一次，之前的代码不知道哪里有小bug一直卡在第4组数据中过不了
这题还是要注意一些细节的，否则就是卡了也找不出来了，因为在两个堆中交换元素太频繁了
#include <cstdio> #include <cstring> const int N = 30000; const int T = 600; int free,busy; int heap[N+10]; int time[N+10]; int pos[N+10]; struct HEAP { int time,n; }Heap[N+10]; void init() { free=N; for(int i=1; i<=N; i++) heap[i]=i; memset(time,-1,sizeof(time)); memset(pos,-1,sizeof(pos)); busy=0; memset(Heap,-1,sizeof(Heap)); } void updata(int p) { struct HEAP tmp=Heap[p]; int key=Heap[p].time , n=Heap[p].n; int par,son,m; for(par=p,son=par*2; son<=busy; son=par*2) { if(son<busy && Heap[son+1].time < Heap[son].time) son++; if(key < Heap[son].time) break; m=Heap[son].n; pos[m]=par; Heap[par]=Heap[son]; par=son; } pos[n]=par; Heap[par]=tmp; } int delHeap() { int n=Heap[1].n; //要返回的内存单元 if(busy==1) { time[n]=pos[n]=-1; busy=0; return n; } time[n]=pos[n]=-1; Heap[1]=Heap[busy--]; updata(1); //从堆的1号节点开始更新 return n; } void insertheap(int n) { int key,par,son; heap[++free]=n; key=n; for(son=free,par=son/2; par>=1; par=son/2) { if(key > heap[par]) break; heap[son]=heap[par]; son=par; } heap[son]=key; } void check(int Time) { while(busy>0 && Heap[1].time < Time) { int n=delHeap(); insertheap(n); } } void delheap() { int key,par,son; key=heap[free]; heap[1]=heap[free--]; for(par=1,son=par*2; son<=free; son=par*2) { if(son<free && heap[son+1] < heap[son]) son++; if(key < heap[son]) break; heap[par]=heap[son]; par=son; } heap[par]=key; } void insertHeap() { struct HEAP tmp=Heap[busy]; int key=Heap[busy].time , n=Heap[busy].n; int par,son,m; for(son=busy,par=son/2; par>=1; par=son/2) { if(key >= Heap[par].time) break; m=Heap[par].n; pos[m]=son; Heap[son]=Heap[par]; son=par; } pos[n]=son; Heap[son]=tmp; } int main() { int Time; char op[5]; int index; init(); while(scanf("%d",&Time)!=EOF) { check(Time); //将占用堆过期元素取出并且放回空闲堆 scanf("%s",op); if(op[0]=='+') { index=heap[1]; delheap(); struct HEAP tmp; int num; tmp.n=index; tmp.time=Time+T-1; time[index]=Time+T-1; busy++; pos[index]=busy; Heap[busy]=tmp; insertHeap(); printf("%d\n",index); } else { scanf("%d",&index); if(time[index]==-1 && pos[index]==-1) { printf("-\n"); continue; } time[index]=Time+T-1; index=pos[index]; Heap[index].time=Time+T-1; updata(index); printf("+\n"); } } return 0; }