求教大佬：CCFCSP 201403-5 任务调度
问题描述
有若干个任务需要在一台机器上运行。它们之间没有依赖关系,因此 可以被按照任意顺序执行。
该机器有两个 CPU 和一个 GPU。对于每个任务,你可以为它分配不 同的硬件资源:
1. 在单个 CPU 上运行。
2. 在两个 CPU 上同时运行。
3. 在单个 CPU 和 GPU 上同时运行。
4. 在两个 CPU 和 GPU 上同时运行。
一个任务开始执行以后,将会独占它所用到的所有硬件资源,不得中 断,直到执行结束为止。第 i 个任务用单个 CPU,两个 CPU,单个 CPU 加 GPU,两个 CPU 加 GPU 运行所消耗的时间分别为 ai,bi,ci 和 di。
现在需要你计算出至少需要花多少时间可以把所有给定的任务完成。
该机器有两个 CPU 和一个 GPU。对于每个任务,你可以为它分配不 同的硬件资源:
1. 在单个 CPU 上运行。
2. 在两个 CPU 上同时运行。
3. 在单个 CPU 和 GPU 上同时运行。
4. 在两个 CPU 和 GPU 上同时运行。
一个任务开始执行以后,将会独占它所用到的所有硬件资源,不得中 断,直到执行结束为止。第 i 个任务用单个 CPU,两个 CPU,单个 CPU 加 GPU,两个 CPU 加 GPU 运行所消耗的时间分别为 ai,bi,ci 和 di。
现在需要你计算出至少需要花多少时间可以把所有给定的任务完成。
输入格式
输入的第一行只有一个正整数 n(1 ≤ n ≤ 40), 是总共需要执行的任 务个数。
接下来的 n 行每行有四个正整数 ai, bi, ci, di(ai, bi, ci, di 均不超过 10), 以空格隔开。
接下来的 n 行每行有四个正整数 ai, bi, ci, di(ai, bi, ci, di 均不超过 10), 以空格隔开。
输出格式
输出只有一个整数,即完成给定的所有任务所需的最少时间。
样例输入
3
4 4 2 2
7 4 7 4
3 3 3 3
4 4 2 2
7 4 7 4
3 3 3 3
样例输出
7
样例说明
有很多种调度方案可以在
7 个时间单位里完成给定的三个任务,以下是其中的一种方案:
同时运行第一个任务(单 CPU 加上 GPU)和第三个任务(单 CPU), 它们分别在时刻 2 和时刻 3 完成。在时刻 3 开始双 CPU 运行任务 2,在 时刻 7 完成。
同时运行第一个任务(单 CPU 加上 GPU)和第三个任务(单 CPU), 它们分别在时刻 2 和时刻 3 完成。在时刻 3 开始双 CPU 运行任务 2,在 时刻 7 完成。
求dalao给个方法，我用自己的方法只能得10分。
/*
渣渣自己的想法
*/
#include
<iostream>
using
namespace std;
#define
N 41
int
a[N];
int
b[N];
int
c[N];
int
d[N];
int
min(int a, int b, int c, int d)
{
int m = a;
if(b < m)
{
m = b;
}
if(c < m)
{
m = c;
}
if(d
< m)
{
m = d;
}
return m;
}
int
max(int a, int b, int c, int d)
{
int m = a;
if(b > m)
{
m = b;
}
if(c > m)
{
m = c;
}
if(d > m)
{
m = d;
}
return m;
}
int
main()
{
int n;
cin>>n;
int time[4][4];
int t;
for(int i = 0; i < n; i++)
{
cin>>a[i]>>b[i]>>c[i]>>d[i];
}
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 4; j++)
{
time[i][j] = 0;
}
}
for(int i = 0; i < n; i++)
{
if(time[0][0] <= time[0][1])
{
time[0][0] += a[i];
}
else
{
time[0][1] += a[i];
}
time[1][0] += b[i];
time[1][1] += b[i];
if(time[2][0] <= time[2][1])
{
time[2][0] += c[i];
}
else
{
time[2][1] += c[i];
}
time[2][2] += c[i];
time[3][0] += d[i];
time[3][1] += d[i];
time[3][2] += d[i];
for(int j = 0 ; j < 4; j++)
{
time[j][3] = max(time[j][0], time[j][1], time[j][2],
time[j][3]);
}
t = min(time[0][3], time[1][3], time[2][3],
time[3][3]);
if(t == time[0][3])
{
for(int j = 1; j < 4; j++)
{
for(int k = 0; k < 3; k++)
{
time[j][k] = time[0][k];
}
}
}
else if(t == time[1][3])
{
for(int j = 0; j < 4; j++)
{
for(int k = 0; k < 3; k++)
{
time[j][k] = time[1][k];
}
}
}
else if(t == time[2][3])
{
for(int j = 0; j < 4; j++)
{
for(int k = 0; k < 3; k++)
{
time[j][k] = time[2][k];
}
}
}
else if(t == time[3][3])
{
for(int j = 0; j < 3; j++)
{
for(int k = 0; k < 3; k++)
{
time[j][k] = time[3][k];
}
}
}
}
cout<<t<<endl;
return 0;
}
网上看的一个代码
/*
网上的
*/
#include<iostream>
#include<string.h>
#include<cmath>
#define M 41
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define inf 1<<30
using
namespace std;
int
time[M][4];
int
c1, c2, com, g, stime;//c1 c2存两个独立cpu的时间（不是同时进行 com存同时进行的时间
g存gpu的时间
int
n;
void
slove(int k, int c1, int c2, int com, int g, int sum)
{
if (k <= n)
{
for (int i = 0; i < 4; i++)
{
switch (i)
{
case 0://1*cpu
c1 < c2 ? slove(k + 1, c1 + time[k][i], c2, com, g,
max(max(c1 + time[k][i], c2) + com, g)) :
slove(k + 1, c1, c2 + time[k][i], com, g,
max(max(c1, c2 + time[k][i]) + com, g));
break;
case 1://2*cpu
slove(k + 1, c1, c2, com + time[k][i], g, max(max(c1,
c2) + com + time[k][i], g));
break;
case 2:
c1 < c2 ? slove(k + 1, c1 + time[k][i], c2, com, g +
time[k][i], max(max(c1 + time[k][i], c2) + com, g + time[k][i])) :
slove(k + 1, c1, c2 + time[k][i], com, g +
time[k][i], max(max(c1, c2 + time[k][i]) + com, g + time[k][i]));
break;
case 3:
slove(k + 1, c1, c2, com + time[k][i], g + time[k][i],
max(max(c1, c2) + com + time[k][i], g + time[k][i]));
break;
}
}
}
else if (stime >sum)
stime = sum;
}
int
main()
{
stime = inf;
c1 = c2 = g = com = 0;//初始化
cin >> n;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < 4; j++)
{
cin >> time[i][j];
}
}
slove(1, 0, 0, 0, 0, 0);
cout << stime << endl;
return 0;
}
但是我用这个提交是0分 = = 有没有dalao也刷过这道题目的，求一下代码
投递传音控股等公司10个岗位 >