编程介的小学生 2017-05-22 10:03 采纳率: 20.3%
浏览 769
已采纳

Load Balancing

Problem Description
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~!

Input
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)

Output
For each test case, first output the N, and follows N numbers mean the job i assign to which server. The servers number count from 0.

Sample Input
2
6 3
2 3 4 6 2 2
6 3
6 4 3 2 2 2

Sample Output
6
0 1 2 0 1 2
6
0 1 1 2 2 2

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-06-05 17:01
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 wincc已组态的变量过多
  • ¥60 如图:直线与椭圆X轴平行,求直线与椭圆任意一点的相切坐标计算公式
  • ¥50 如何用python使用opencv里的cv::cudacodec::VideoWriter函数对视频进行GPU硬编码
  • ¥100 c#solidworks 二次开发 工程图自动标边线法兰 等折弯尺寸怎么标
  • ¥15 halcon DrawRegion 提示错误
  • ¥15 FastAPI Uvicorn启动显示404
  • ¥15 centos7.9脚本,怎么排除特定的访问记录
  • ¥15 关于#Django#的问题:我的静态文件呢?
  • ¥15 关于CPLEX的问题,请专家解答
  • ¥15 cocos的点击事件 怎么穿透到 原生fragment上。