1. 用贪心分别算出A单独加工n个工件的时间f1, 和B单独加工n个工件的时间f2
2. 用f1 的最小值 + f2 最大值 , 用平均贪心的思想. 再比较最大值为第二问的解.
/**//*
ID: lorelei3
TASK: job
LANG: C++
*/
#include <fstream>
#include <algorithm>
#include <functional>
using namespace std;
const int MAXN = 1005;
const int MAXM = 35;
int t1[MAXM], t2[MAXM], w1[MAXM], w2[MAXM], f1[MAXN], f2[MAXN];
int main()
{
int i,j, n, m1, m2;
ifstream fin("job.in");
ofstream fout("job.out");
fin>>n>>m1>>m2;
for(i=1; i<=m1; ++i)
fin>>t1[i];
for(i=1; i<=m2; ++i)
fin>>t2[i];
for(i=1; i<=n; ++i){
int min=1;
for(j=2; j<=m1; ++j)
if(w1[j]+t1[j] < w1[min]+t1[min])
min=j;
w1[min] += t1[min];
f1[i] = w1[min];
min=1;
for(j=2; j<=m2; ++j)
if(w2[j]+t2[j] < w2[min]+t2[min])
min =j;
w2[min] += t2[min];
f2[i] = w2[min];
}
sort(f1+1, f1+n+1, less<int>());
sort(f2+1, f2+n+1, greater<int>());
int ans1 = f1[n], ans2 = 0;
for(i=1; i<=n; ++i)
if(f1[i]+f2[i] > ans2)
ans2 = f1[i]+f2[i];
fout<<ans1<<" "<<ans2<<endl;
return 0;
}posted on 2011-01-25 17:10
小阮 阅读(820)
评论(2) 编辑 收藏 引用 所属分类:
USACO