Hdu 2850 Load Balancing (贪心优先队列)

本是古典何须时尚 2021-11-01 10:40 264阅读 0赞

题意：n个任务，m台服务器，给出每个任务的耗时，分配工作到服务器中，使他们各台服务器间总处理时间的最大值与最小值的差最小

思路：贪心，优先队列，先处理耗时多的任务，再处理耗时少的任务。先对耗时从大到小排序，然后每次更新每个机器的最大工作时间，每次取出总耗时最少的服务器分配新的任务。

#include <cstdio>
    #include <algorithm>
    #include <queue>
    using namespace std;
    
    struct Edge
    {
         int cost,id;
         Edge () {}
         Edge (int a,int b)
    	 {
             cost = a,id = b;
         }
    	 void Get (int _i)
    	 {
    		 id=_i;
    		 scanf("%d",&cost);
    	 }
    	 bool operator < (const Edge &y) const
    	 {
    		 return cost>y.cost;
    	 }
    }data[100005];
    
    int ans[100005],n,m;
    
    int main ()
    {
    	int T,i;
    	scanf("%d",&T);
    	while (T--)
    	{
    		priority_queue<Edge> que;
    		scanf("%d%d",&n,&m);
    		for (i=0;i<n;i++)
    			data[i].Get (i);
    		sort (data,data+n);
    		Edge temp;    //temp的id值表示它是由哪个机器处理的
    		for (i=0;i<n;i++)
    			if (i<m)     //都还没有任务的时候
    			{
    				que.push(Edge(data[i].cost,i));   //将时间和处理标号一起入队
    				ans[data[i].id]=i;
    			}
    			else
    			{
    				temp=que.top ();
    				ans[data[i].id]=temp.id;
    				que.pop();
    				que.push(Edge(temp.cost+data[i].cost,temp.id));//将目前用掉的总时间和处理标号入队
    			}
    		printf("%d\n",n);
    		for (i=0;i<n;i++)
    			printf(i==n-1?"%d\n":"%d ",ans[i]);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，264人围观）

还没有评论，来说两句吧...

相关阅读

相关 codeforces 603 C. Load Balancing 贪心

C. Load Balancing time limit per test 2 seconds memory limit per test 256 megabytes

清疚/ 2022年08月18日 15:22/ 0 赞/ 52 阅读

相关 51nod 1163 （贪心+优先队列）

有N个任务，每个任务有一个最晚结束时间以及一个对应的奖励。在结束时间之前完成该任务，就可以获得对应的奖励。完成每一个任务所需的时间都是1个单位时间。有时候完成所有任务是不可能的

快来打我*/ 2022年07月27日 14:48/ 0 赞/ 170 阅读

相关 51nod 1191(贪心+优先队列)

有N只兔子，每只有一个血量B\[i\]，需要用箭杀死免子。有M种不同类型的箭可以选择，每种箭对兔子的伤害值分别为D\[i\]，价格为P\[i\](1 <= i <= M)。假设

怼烎@/ 2022年07月27日 13:39/ 0 赞/ 163 阅读

相关 51nod 1428 （贪心+优先队列）

![Image 1][]有若干个活动，第i个开始时间和结束时间是\[Si,fi)，同一个教室安排的活动之间不能交叠，求要安排所有活动，最少需要几个教室？ Input

本是古典何须时尚/ 2022年07月26日 05:28/ 0 赞/ 180 阅读

相关 51nod 1117(贪心+优先队列)

一位老木匠需要将一根长的木棒切成N段。每段的长度分别为L1,L2,......,LN（1 <= L1,L2,…,LN <= 1000，且均为整数）个长度单位。我们认为切割时仅在

傷城~/ 2022年07月26日 01:29/ 0 赞/ 196 阅读

相关【hdu1873】优先队列

Description 看病要排队这个是地球人都知道的常识。不过经过细心的0068的观察，他发现了医院里排队还是有讲究的。0068所去的医院有三个医生（汗，这么少）同时

￡神魔★判官ぃ/ 2022年07月18日 04:04/ 0 赞/ 145 阅读

相关 HDU 1062(优先队列+BFS)

问题描述: The Princess has been abducted by the BEelzebub feng5166, our hero Ignatius has t

梦里梦外;/ 2022年06月08日 14:58/ 0 赞/ 172 阅读

相关 #433 - C. Planning（贪心，优先队列）

-------------------- 题目连接：[http://codeforces.com/contest/854/problem/C][http_codeforces

落日映苍穹つ/ 2022年06月08日 05:20/ 0 赞/ 185 阅读

相关 Expedition POJ - 2431 (贪心+优先队列)

A group of cows grabbed a truck and ventured on an expedition deep into the jungle. Bein

叁歲伎倆/ 2022年03月06日 04:16/ 0 赞/ 218 阅读

相关 Hdu 2850 Load Balancing (贪心优先队列)

题意：n个任务，m台服务器，给出每个任务的耗时，分配工作到服务器中，使他们各台服务器间总处理时间的最大值与最小值的差最小思路：贪心，优先队列，先处理耗时多的任务，再处理耗时

本是古典何须时尚/ 2021年11月01日 10:40/ 0 赞/ 265 阅读