题目描述
假设有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为ti。试设计一个算法找出完成这n个任务的最佳调度,使得完成全部任务的时间最早。 对任意给定的整数n和k,以及完成任务i需要的时间为ti,i=1~n。编程计算完成这n个任务的最佳调度。
时限3000ms
输入格式
第一行有2 个正整数n和k。第2 行的n个正整数是完成n个任务需要的时间。
输出格式
将计算出的完成全部任务的最早时间输出
输入输出测试点
输入 #1
复制
7 3
2 14 4 16 6 5 3
输出 #1
复制
17
说明
n<20, k < 10。
其他数字不超过100。
我的错误代码:
#include <bits/stdc++.h>
using namespace std;
int n, k, ans = 1000;
int a[250];
int maxt[250];
void dfs(int m)
{
if (m == n)
{
int minT = 0;
for (int i = 0; i < k; i ++ )
minT = max(minT, maxt[i]);
ans = min(ans, minT);
return ;
}
for (int i = 0; i < k; i ++ )
{
if (maxt[i] + a[m] >= ans) continue;
maxt[i] += a[m];
dfs(m + 1);
maxt[i] -= a[m];
}
}
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i ++ ) cin >> a[i];
dfs(0);
cout << ans;
return 0;
}