作者在 2012-03-19 15:00:13 发布以下内容
某工厂有n个独立的作业，由m台相同的机器进行加工处理。作业i所需的加工时间为ti，任何作业在被处理时不能中断，也不能进行拆分处理。现厂长请你给他写一个程序：算出n个作业由m台机器加工处理的较短时间。
输入第一行T（1<T<100)表示有T组测试数据。每组测试数据的第一行分别是整数n，m（1<=n<=10000，1<=m<=100），接下来的一行是n个整数ti（1<=t<=100)。输出所需的较短时间。（提示：不一定是最优解）样例输入2 2 2 1 5 6 3 2 5 13 15 16 20样例输出5 28#include <stdio.h>
int main()
{
int t,n,m,ti[10000];
scanf("%d",&t);
while(t--)
{
int i,j,co[100]={0},max,k,min;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%d",&ti[i]);
for(i=0;i<n;i++) //对时间进行从大到小的排序
{
for(k=i,max=ti[i],j=i;j<n;j++)
if(ti[j]>max)
{
max=ti[j];
k=j;
}
ti[k]=ti[i];
ti[i]=max;
}
if(n<=m) //当机器数目多时，直接输出最大时间，极为所需最少时间
{
printf("%d\n",ti[0]);
continue;
}
else //机器数目少时
{
for(i=0;i<n;i++) //思路：总是把任务交给当前最空闲的机器
{
min=co[0];
for(k=0,j=1;j<m;j++)
if(co[j]<min)
{
min=co[j];
k=j;
}
co[k]+=ti[i];
}
}
max=co[0];
for(i=1;i<m;i++)
if(co[i]>max)
max=co[i];
printf("%d\n",max);
}
return 0;
}
int main()
{
int t,n,m,ti[10000];
scanf("%d",&t);
while(t--)
{
int i,j,co[100]={0},max,k,min;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%d",&ti[i]);
for(i=0;i<n;i++) //对时间进行从大到小的排序
{
for(k=i,max=ti[i],j=i;j<n;j++)
if(ti[j]>max)
{
max=ti[j];
k=j;
}
ti[k]=ti[i];
ti[i]=max;
}
if(n<=m) //当机器数目多时，直接输出最大时间，极为所需最少时间
{
printf("%d\n",ti[0]);
continue;
}
else //机器数目少时
{
for(i=0;i<n;i++) //思路：总是把任务交给当前最空闲的机器
{
min=co[0];
for(k=0,j=1;j<m;j++)
if(co[j]<min)
{
min=co[j];
k=j;
}
co[k]+=ti[i];
}
}
max=co[0];
for(i=1;i<m;i++)
if(co[i]>max)
max=co[i];
printf("%d\n",max);
}
return 0;
}