P9214题解

· · 题解

一道不错的练优先队列的题目。

这篇题解讲得比较细，非常适合新手。

题目大意：

有 n 个评测节点来完成 m 个评测任务，每个任务需要时间 t，每次将第 i 个任务分配给总用时最少的评测节点，若总用时相同则分配到编号较小的节点，输出每个节点所分配的任务编号，没分配到任务则输出 0。

思路：

看到“每次都分配到总用时最少的评测节点”这句话，我想都没想，直接用优先队列。

步骤：

  1. 开一个小根堆。堆中要维护两个元素，一个是节点编号，一个是总用时，所以直接开一个结构体。

  2. 将 n 个节点全部压入堆，此时总用时为 0。

  3. 每次读入一个时间 t，就弹出堆顶元素，将此节点的总用时加上 t，再压回堆中，用一个 vector 来存储每次分配到的编号。

  4. 最后输出 vector 当中存储的值就可以了。

如果还是不懂，就看代码吧！

切勿抄袭！！！

代码：

#include <bits/stdc++.h>
using namespace std;
inline int read(){//快读
    int a=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if  (c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        a=a*10+(c-'0');
        c=getchar();
    }
    return f*a;
}
int n,m;
vector<int>a[500005];//记录答案的vector(不能用数组，n*m会爆空间)
struct node{//结构体
    long long s;//总用时，别忘了开long long(t<=10^9,m<=10^5,爆int了)
    int op;//节点编号
    bool operator >(const node &k)const{//重载运算符
        if(s!=k.s)return s>k.s;//如果用时不相同，就按用时排
        else return op>k.op;//否则按节点编号排
    }
};
priority_queue<node,vector<node>,greater<node> >q;//小根堆
//以上为步骤1
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++){//初始化(步骤2)
        node k;
        k.op=i,k.s=0;
        q.push(k);
    }
    for(int i=1;i<=m;i++){//处理(步骤3)
        int t=read();
        node k=q.top();//弹出堆顶
        q.pop();
        k.s+=t;//总用时加上t
        q.push(k);//压回堆
        a[k.op].push_back(i);//加入答案中
    }
    for(int i=1;i<=n;i++){//输出答案(步骤4)
        for(int j=0;j<a[i].size();j++)
            printf("%d ",a[i][j]);
        if(a[i].size()==0)printf("0");//如果没有分配到，输出0
        printf("\n");
    }
    return 0;
}

完结~