任务调度Min-Max 算法C语言代码
时间: 2024-05-07 14:20:06 浏览: 11
以下是一个简单的 Min-Max 算法的 C 语言代码:
```
#include <stdio.h>
int main()
{
int n, m;
printf("请输入任务数和机器数:");
scanf("%d %d", &n, &m);
int task[n], machine[m];
for(int i = 0; i < n; i++)
{
printf("请输入第 %d 个任务的执行时间:", i+1);
scanf("%d", &task[i]);
}
int sum = 0;
for(int i = 0; i < n; i++)
sum += task[i];
int max = 0;
for(int i = 0; i < n; i++)
{
if(task[i] > max)
max = task[i];
}
int min_time = (sum + m - 1) / m;
if(min_time < max)
min_time = max;
int max_time = sum;
while(min_time < max_time)
{
int mid_time = (min_time + max_time) / 2;
int now_time = 0, now_machine = 0;
for(int i = 0; i < n; i++)
{
if(now_time + task[i] <= mid_time)
now_time += task[i];
else
{
now_machine++;
now_time = task[i];
}
}
if(now_machine < m)
max_time = mid_time;
else
min_time = mid_time + 1;
}
printf("最小完成时间为:%d\n", min_time);
return 0;
}
```
该算法首先输入任务数和机器数,然后输入每个任务的执行时间。接着计算出所有任务的总执行时间和执行时间最长的任务,然后使用二分查找来确定最小完成时间。在二分查找时,我们先计算出中间时间,然后使用贪心算法来计算出在这个时间下需要多少台机器。如果需要的机器数小于或等于输入的机器数,则说明中间时间可以更小,因此更新最大时间,否则更新最小时间。最终,输出最小完成时间。