自动搬运

查看原文

来自洛谷，原作者为

	2021sunzishan 情愿一生如梦游

搬运于2025-08-24 22:46:25，当前版本为作者最后更新于2023-07-31 22:32:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

题目大意：

有 $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;
}

完结~