堆

然鹅我用的一直是stl。。。

优先队列讲解

P1801 黑匣子_NOI导刊2010提高（06）

用两个堆来存储

Q1是大根堆有当前cnt-1个值（get第cnt大值

Q2是小根堆

每次有值先塞进Q1 然后把Q1中最大的值给Q2

Get后把Q2堆顶扔进Q1

 1     for(int i = 1; i <= n; i++){
 2         q1.push(a[i]); 
 3         int top = q1.top(); q1.pop();
 4         q2.push(top); 
 5         while(u[ucnt] == i){
 6             top = q2.top(); q2.pop();
 7             printf("%d
", top);
 8             q1.push(top); 
 9             ucnt++;
10         }
11     }

View Code

P2278 [HNOI2003]操作系统

每有一个新的任务来

就把它和上一个任务出现时间间隔分配出去

按优先级逐个分配

注意同优先级比较出现时间

最后记得将剩余的任务分配出去

 1     while(scanf("%d%d%d%d", &a, &b, &c, &d) != EOF){
 2         int time = b - pre; pre = b;
 3         cnt += time;
 4         while(!q.empty() && time){
 5             Node top = q.top(); q.pop();
 6             if(top.t <= time){
 7                 time -= top.t;
 8                 top.t = 0;
 9                 printf("%d %d
", top.id, cnt - time);
10             }
11             else {
12                 top.t -= time;
13                 time = 0;
14                 q.push(top);
15             } 
16         }
17         q.push((Node){a, b, c, d});
18     }
19     while(!q.empty()){
20         Node top = q.top(); q.pop();
21         cnt += top.t;
22         printf("%d %d
", top.id, cnt);
23     }

View Code

P1631 序列合并

先准备好a[i] + b[1] 扔进堆里

取a[i] + b[j]的话就把a[i] + b[j + 1]扔进去

1     for(int i = 1; i <= n; i++){
2         Node top = q.top(); q.pop();
3         printf("%d ", top.w);
4         q.push((Node){a[top.x] + b[top.y + 1], top.x, top.y + 1});
5     }

View Code

P2085 最小函数值

这题同上只不过换成函数了而已