poj 1193

地址：http://poj.org/problem?id=1193

题意：中文，模拟进程调度。

mark：大模拟！手写堆+链表爽到爆！很考验基本功！写完竟然TLE结果发现是链表写搓了！

思路大概是，内存用链表来组织，整个程序建立一个事件队列来驱动，事件队列是优先队列，按时间从小到大排序。一开始把所有任务丢到事件队列里；等待队列队首的任务在每次release一段内存的时候判断是否run。

比较容易错的地方有：

1.release了一段内存后从等待队列取任务判断是否能执行时，若第一个等待队列的任务能执行，要继续循环判断等待队列里下一个任务是否能执行……

3
1 3 2
2 1 1
2 1 1
0 0 0

输出

2.要完全释放当前时间点的所有内存才可以判断等待队列里的任务运行情况。

11
1 4 1
1 4 1
1 4 1
1 1 1
1 6 1
0 0 0

输出

PS：不存在P[i] = 0的情况。

代码：

  1 # include <stdio.h>
  2 # include <stdlib.h>
  3 
  4 
  5 #define SWAP(a,b) (tmp=a, a=b, b=tmp)
  6 
  7 
  8 int T[10010], M[10010], P[10010] ;
  9 int type[10010] ;
 10 int ans1, ans2 ;
 11 
 12 /*message queue --- priority queue*/
 13 int msgQueue[10010], mqlen ;
 14 /*message queue end*/
 15 
 16 
 17 /*wait list*/
 18 int wait_rear, wait_front ;
 19 int wait_list[10010] ;
 20 /*wait list end*/
 21 
 22 
 23 /*memory alloc*/
 24 int mem[10010] ;
 25 /*memory alloc end*/
 26 
 27 
 28 int cmp (int a, int b)
 29 {
 30     if (T[a] != T[b]) return T[a] - T[b] ;
 31     if (type[b] != type[a]) return type[b] - type[a] ;
 32     return a-b ;
 33     //return mem[b] - mem[a] ;
 34 //    return type[b]-type[a] ;
 35 }
 36 
 37 
 38 void imq(int x, int t)
 39 {
 40     int p = mqlen, q = p/2, tmp ;
 41     type[x] = t ;
 42     msgQueue[mqlen++] = x ;
 43     while (q)
 44         if (cmp(msgQueue[p],msgQueue[q])<0)
 45             SWAP(msgQueue[p],msgQueue[q]), p=q, q/=2 ;
 46         else break ;
 47 }
 48 
 49 
 50 void mqheapify(int x)
 51 {
 52     int p = x, q, tmp ;
 53     q = x*2 ;
 54     if (q < mqlen && cmp(msgQueue[q], msgQueue[p])<0) p = q ;
 55     q = x*2+1 ;
 56     if (q < mqlen && cmp(msgQueue[q], msgQueue[p])<0) p = q ;
 57     if (p != x)
 58     {
 59         SWAP(msgQueue[p], msgQueue[x]) ;
 60         mqheapify (p) ;
 61     }
 62 }
 63 
 64 
 65 int dmq()
 66 {
 67     int rtn = msgQueue[1], tmp ;
 68     mqlen-- ;
 69     SWAP(msgQueue[1], msgQueue[mqlen]) ;
 70     mqheapify (1) ;
 71     return rtn ;
 72 }
 73 
 74 
 75 typedef struct MEM_NODE{
 76     int hi, lo ;
 77     MEM_NODE *prev, *next ;
 78 }MEM_NODE ;
 79 
 80 
 81 MEM_NODE head ;
 82 
 83 
 84 void mem_init(int size){
 85     MEM_NODE *p = (MEM_NODE*)malloc(sizeof (MEM_NODE)) ;
 86     p->hi = size-1, p->lo = 0, p->prev = &head, p->next = NULL ;
 87     head.next = p ;
 88 }
 89 
 90 void mem_delete(MEM_NODE* p)
 91 {
 92     if (p->next != NULL){
 93         mem_delete(p->next) ;
 94         p->next = NULL ;
 95     }
 96     free (p) ;
 97 }
 98 
 99 
100 int mem_find(int size)
101 {
102     MEM_NODE* p = NULL ;
103     for (p = head.next ; p ; p = p->next)
104     {
105         if (p->hi - p->lo + 1 >= size)
106             return p->lo ;
107     }
108     return -1 ;
109 }
110 
111 
112 void mem_delete_node(MEM_NODE *p)
113 {
114     MEM_NODE *prev = p->prev, *next = p->next ;
115     //if (prev != &head) 
116     prev->next = next ;
117     if (next != NULL) next->prev = prev ;
118     free (p) ;
119 }
120 
121 
122 void mem_alloc(int lo, int size)
123 {
124     MEM_NODE* p = NULL ;
125     for (p = head.next ; p ; p = p->next)
126         if (p->lo == lo) {
127             p->lo += size ;
128             break ;
129         }
130     if (p->lo > p->hi) mem_delete_node(p) ;
131 }
132 
133 
134 MEM_NODE* mem_merge(MEM_NODE* p)
135 {
136     MEM_NODE*q = p->next ;
137     if (q == NULL) return p ;
138     if (p->hi+1 != q->lo) return q ;
139     p->hi = q->hi;
140     mem_delete_node(q) ;
141     return p ;
142 }
143 
144 
145 void mem_release (int lo, int size)
146 {
147     MEM_NODE *p = NULL, *q = NULL ;
148     
149     q = &head, p = q->next ;
150     while (p != NULL && p->hi < lo)
151         q = p, p = p->next ;
152     p = (MEM_NODE*)malloc(sizeof(MEM_NODE)) ;
153     p->lo = lo, p->hi = lo+size-1 ;
154     p->next = q->next ;
155     q->next = p ;
156     p->prev = q ;
157     if (p->next != NULL) p->next->prev = p ;
158     if (q != &head) p = mem_merge(q) ;
159     mem_merge(p) ;
160 }
161 
162 
163 
164 int try_alloc(int x)
165 {
166     int mem_num = mem_find(M[x]) ;
167     if (mem_num == -1) return 0 ;
168     mem[x] = mem_num ;
169     mem_alloc (mem_num, M[x]) ;
170     T[x] += P[x] ;
171     imq (x, 1) ;
172     return 1 ;
173 }
174 
175 
176 void alloc(int x)
177 {
178     if (!try_alloc(x))
179     {
180         wait_list[wait_rear++] = x ;
181         if (wait_rear > ans2) ans2 = wait_rear ;
182     }
183 }
184 
185 
186 void release(int x){
187     int tt = T[x] ;
188     if (tt > ans1) ans1 = tt ;
189     while (1)
190     {
191         mem_release(mem[x], M[x]) ;
192         if (mqlen == 1) break ;
193         if (type[msgQueue[1]]==0) break ;
194         if (T[msgQueue[1]] != tt) break ;
195         x = dmq() ;
196     }
197     while (wait_front != wait_rear)
198     {
199         x = wait_list[wait_front] ;
200         T[x] = tt ;
201         if (try_alloc(x)) wait_front++ ;
202         else break ;
203     }
204 }
205 
206 
207 int main ()
208 {
209     int n, m, i, x ;
210     
211     while (~scanf ("%d", &n))
212     {
213         m = 0 ; wait_rear = wait_front = 0 ;
214         mem_init(n) ;
215         ans1 = ans2 = 0 ;
216         mqlen = 1 ;
217         while (~scanf ("%d%d%d", &T[m], &M[m], &P[m]) && (T[m]||M[m]||P[m])) m++ ;
218         for (i = 0 ; i < m ; i++) imq(i, 0) ;
219         while (mqlen != 1)
220         {
221             if (type[x=dmq()] == 0) alloc(x) ;
222             else release (x) ;
223         }
224         mem_delete(head.next) ;
225         printf ("%d
%d
", ans1, ans2) ;
226     }
227     return 0 ;
228 }