维护两个堆，一个记录空闲内存，一个记录使用中的内存
1 #include <iostream>
2 using namespace std;
3 const int maxn=30011;
4 const int T=600;
5 int freea[maxn],busy[maxn];
6 int freeanum,busynum;
7 int usetime[maxn];
8 int pos[maxn];
9 int ti;
10
11 void upfreea(int x){
12 int rc=freea[x];
13 int i=x/2;
14 while (rc<freea[i]){
15 freea[x]=freea[i];
16 x=i;
17 i/=2;
18 }
19 freea[x]=rc;
20 }
21
22 void upbusy(int x){
23 int rc=busy[x];
24 int i=x/2;
25 while (usetime[rc]<usetime[busy[i]]){
26 busy[x]=busy[i];
27 pos[busy[i]]=x;
28 x=i;
29 i/=2;
30 }
31 busy[x]=rc;
32 pos[rc]=x;
33 }
34
35 void downfreea(int x){
36 int rc=freea[x];
37 for (int i=x*2;i<=freeanum;i*=2){
38 if (freea[i]>freea[i+1]&&i<freeanum) ++i;
39 if (rc<freea[i]) break;
40 freea[x]=freea[i];
41 x=i;
42 }
43 freea[x]=rc;
44 }
45
46 void downbusy(int x){
47 int rc=busy[x];
48 int i=x*2;
49 for (;i<=busynum;i*=2){
50 if (usetime[busy[i]]>usetime[busy[i+1]]&&i<busynum) ++i;
51 if (usetime[rc]<=usetime[busy[i]]) break;
52 busy[x]=busy[i];
53 pos[busy[i]]=x;
54 x=i;
55 }
56 busy[x]=rc;
57 pos[rc]=x;
58 }
59
60 void inbusy(int x){
61 ++busynum;
62 busy[busynum]=x;
63 upbusy(busynum);
64 }
65
66 void infreea(int x){
67 ++freeanum;
68 freea[freeanum]=x;
69 upfreea(freeanum);
70 }
71
72 void outbusy(){
73 int nx=busy[1];
74 infreea(nx);
75 pos[nx]=0;
76 busy[1]=busy[busynum];
77 --busynum;
78 if (busynum>1)downbusy(1);
79 }
80
81 int outfreea(){
82 int nx=freea[1];
83 freea[1]=freea[freeanum];
84 --freeanum;
85 downfreea(1);
86 return nx;
87 }
88
89 void check(int now){
90 if (busynum==0) return;
91 while (now-usetime[busy[1]]>=T&&busynum>0) outbusy();
92 }
93
94 void use(int now){
95 int x=outfreea();
96 usetime[x]=now;
97 inbusy(x);
98 printf("%d\n",x);
99 }
100
101 void request(int num,int now){
102 if (pos[num]==0) printf("-\n");
103 else{
104 printf("+\n");
105 usetime[num]=now;
106 downbusy(pos[num]);
107 }
108 }
109
110 int main(){
111 for (int i=1;i<maxn;++i) freea[i]=i;
112 freeanum=maxn-1;
113 while (scanf("%d",&ti)!=EOF){
114 char ch;
115 scanf(" %c",&ch);
116 check(ti);
117 if (ch=='+'){
118 use(ti);
119 }
120 if (ch=='.'){
121 int x;
122 scanf("%d",&x);
123 request(x,ti);
124 }
125 }
126 }
127
posted on 2008-11-05 19:16
Joseph 阅读(143)
评论(0) 编辑 收藏 引用