首页 > ACM题库 > HDU-杭电 > HDU 2850-Load Balancing-贪心-[解题报告]HOJ
2014
02-17

HDU 2850-Load Balancing-贪心-[解题报告]HOJ

Load Balancing

问题描述 :

In the Wide Web World, Which web server was popular in web site? Apache, nginx, lighttpd? Baidu.com use Apache, and many web sites like 163.com use nginx. Why? Its configuration is very simple, and it has very powerful load balancing features.

How does load balancing work? Load balancing is a technique to spread work between two or more computers in order to get optimal resource utilization, maximize throughput, and minimize response time. Wiskey very curious about this technology and he wants to build a simple load balancing model.

He define the web site has M servers, and N jobs need be done. Each job has a processing time T; we seek to assign each job to one of the servers so that the loads placed on all servers are as "balanced" as possible. The "balanced" mean the Minimize it (max {TMi} – min {TMj}). TMi is the server i total time cost.

But, as Wiskey Know, this scheduling problem of finding an assignment of minimum gap is NP-hard.

Can you write a better load balancing than Wiskey? Challenge it~!

输入:

The first integer C represents the number of cases, And C cases followed.

Each test case contains a single integer N (1<=N<=100000) and M (1<=M<=100). The next N line contains integers, meaning the time of job T1, T2Tn. (1<=Ti<=1000000)

输出:

The first integer C represents the number of cases, And C cases followed.

Each test case contains a single integer N (1<=N<=100000) and M (1<=M<=100). The next N line contains integers, meaning the time of job T1, T2Tn. (1<=Ti<=1000000)

样例输入:

2
6 3
2 3 4 6 2 2
6 3
6 4 3 2 2 2

样例输出:

6
0 1 2 0 1 2
6
0 1 1 2 2 2
Hint
Hint This problem is special judge, if your assign plan (max {TMi} -min {TMj}) <= my answer + 1000, it be consider Accept.

题意: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;
}

解题参考:http://blog.csdn.net/whyorwhnt/article/details/9916943