优先队列-负载均衡

题目用到了优先队列的一些操作，如果知道操作就比较简单了，所以有必要记录一下。

题目来源

www.acwing.com/problem/content/3495/

题目

有 n 台计算机，第 i 台计算机的运算能力为$ v_i$。

有一系列的任务被指派到各个计算机上，第 i 个任务在 $a_i$ 时刻分配，指定计算机编号为 $b_i$，耗时为 $c_i$ 且算力消耗为 $d_i$。

如果此任务成功分配，将立刻开始运行，期间持续占用 bi 号计算机 $d_i$ 的算力，持续 $c_i$ 秒。

对于每次任务分配，如果计算机剩余的运算能力不足则输出 −1，并取消这次分配，否则输出分配完这个任务后这台计算机的剩余运算能力。

输入格式

输入的第一行包含两个整数 n,m，分别表示计算机数目和要分配的任务数。

第二行包含 n 个整数$ v_1,v_2,⋅⋅⋅v_n$，分别表示每个计算机的运算能力。

接下来 m 行每行 4 个整数 $a_i,b_i,c_i,d_i$，意义如上所述。数据保证 $a_i$ 严格递增，即 $a_i<a_i+1$。

输出格式

输出 m 行，每行包含一个数，对应每次任务分配的结果。

数据范围

对于 20% 的评测用例，$n,m≤200$。

对于 40% 的评测用例，$n,m≤2000$。

对于所有评测用例，$1≤n,m≤200000，$$1≤a_i,c_i,d_i,v_i≤10^9$，$1≤b_i≤n$。

输入样例：

输出样例：

2
-1
-1
1
-1
0

样例解释

时刻 1，第 1 个任务被分配到第 1 台计算机，耗时为 5，这个任务时刻 6 会结束，占用计算机 1 的算力 3。

时刻 2，第 2 个任务需要的算力不足，所以分配失败了。

时刻 3，第 1 个计算机仍然正在计算第 1 个任务，剩余算力不足 3，所以失败。

时刻 4，第 1 个计算机仍然正在计算第 1 个任务，但剩余算力足够，分配后剩余算力 1。

时刻 5，第 1 个计算机仍然正在计算第 1,4 个任务，剩余算力不足 4，失败。

时刻 6，第 1 个计算机仍然正在计算第 4 个任务，剩余算力足够，且恰好用完。

AC代码

#include <iostream>
#include <queue>
using namespace std;
const int MAX = 200005;
typedef pair<int,int> PII;  //加入的工作，存储形式为<结束时刻，算力>，前一个参数存放结束时刻，后一个参数存放占用的算力
int computer[MAX];          //维护一个电脑算力数组
priority_queue<PII,vector<PII>,greater<PII>> pq[MAX];//优先队列数组，为每个电脑目标创建一个优先队列存取加入的PII类型的工作
int main(){
    int n,m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++) {
        cin>>computer[i];
    }
    int a,aim,usetime,usev; //时刻，目标，消耗时间，消耗算力
    while(m--) {
        cin>>a>>aim>>usetime>>usev;
        //循环处理该目标电脑的工作，如果工作结束时间<=该时刻则恢复算力清除这一工作
        while(pq[aim].size() && (pq[aim].top().first <= a)){
            computer[aim]+=pq[aim].top().second;//恢复算力
            pq[aim].pop();//弹出任务
        }
        //处理完后，判断当前安排的工作是否还可以执行
        if(computer[aim] >= usev){
            pq[aim].push({a+usetime,usev});//加入任务
            computer[aim]-=usev;//更新算力
            cout<<computer[aim]<<endl;
        }else{
            cout<<-1<<endl;
        }
    }
    return 0;
}

优先队列

优先队列虽然称为队列，但其底层实现原理是基于堆的设计思想，还没详细学，这里先粗略的记录下基础操作，之后学了再更新

所在库:queue
操作和队列相似
c++中的定义 priority_queue< 数据类型，容器(vector<>),排序方式(greater<>,less<>)>
- greater<>大顶堆-降序
- less<>小顶堆-升序