注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

xmu1107.并行机器调度问题  

2011-11-17 16:31:06|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1107.并行机器调度问题
Time Limit: 1000 MS         Memory Limit: 65536 K
Total Submissions: 793 (218 users)         Accepted: 299 (207 users)
[ My Solution ]

Description

  给定n个任务J1...Jn和m台机器M1,...Mm.对于每个任务Ji,其处理时间为ti>0,而且必须由一台机器不间断的处理,每台机器在一个时间段里最多处理一个任务。
  并行机器调度问题就是如何将任务分配给机器,使得处理完所有任务的时间最短。(即最后一个任务的完成时间最短)
  请设计一个1.33-近似算法,输出近似最短时间,即定义最优解为C,只要输出在[C , 1.33 * C]的范围内都可以“Accept”。

 

Input

  输入第一行为两个正整数n ,m(1 <= n <= 20 , 1 <= m <= 5),表示作业个数和机器个数。
  第二行包括n个正整数,第i个整数表示完成作业ji所需要的时间。

Output

  输出一个整数表示近似最短时间。

Sample Input

6 2
10 8 3 1 7 5

Sample Output

17

Source
xmu @ kantianfadai


数据比较弱,只要用贪心就可以搞定了。先把时间从大到小排序,计算每次时间最少的,加上更新的时间,最后求最大的时间即排序后的第一个值就是答案了。
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

bool cmp(int a, int b)
{
        return a > b;
}

int main()
{
        int n, m, i, j;
        int t[21], a[21] = {0};
        scanf("%d%d", &n, &m);
        for(i = 0; i < n; i++)
                scanf("%d", &t[i]);
        sort(t, t + n, cmp);
        for(i = 0; i < m; i++)
                a[i] = t[i];
        for(j = m; j < n; j++)
        {
                sort(a, a + m, cmp);
                a[m-1] += t[j];
        }
        sort(a, a+m, cmp);
        printf("%d\n", a[0]);
return 0;
}

  评论这张
 
阅读(424)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017