果断贪心第一问:
第一问代码
/*
USER:zyn19961
LANG:C++
TASK:job
*/
#include<cstdio>
#include<cstring>
//超囧,所有的used都打成了uesd了.
int A[31],B[31];
int times[31];
int uesd[31];
int inline min(int a,int b){return a<b?a:b;}
int main(){
freopen("job.in","r",stdin);
freopen("job.out","w",stdout);
int n,a,b;
int min,minl;
scanf("%d %d %d",&n,&a,&b);
for(int i=1;i<=a;i++){
scanf("%d",&A[i]);
uesd[i]=A[i];
times[i]=0;
}
for(int i=1;i<=b;i++)
scanf("%d",&B[i]);
for(int i=1;i<=n;i++){
min=uesd[1];
minl=1;
for(int k=2;k<=a;k++)
if(uesd[k]<min){
minl=k;
min=uesd[k];
}
times[minl]++;
uesd[minl]+=A[minl];
}
min=uesd[1]-A[1];
for(int k=2;k<=a;k++)
if(min<uesd[k]-A[k])//这里是max
min=uesd[k]-A[k];
printf("%d\n",min);
fclose(stdin);
fclose(stdout);
return 0;
}
仔细想了一下第二问也应该是贪心,但感觉在第一问的基础上做无从下手。
其实第一问的代码是以机器为单位来求最长时间的,对于第二问就无法照搬了。
但其实可以以每个产品为单位,计算出第i个加工好的产品所需时间。
a中最早的产品,作为b中所花时间最多的产品来加工,这样保证结果最优。
搞笑的AC代码
/*
USER:zyn19961
LANG:C++
TASK:job
*/
#include<cstdio>
#include<cstring>
//uesd 表示a
//used 表示b
int timea[1001],timeb[1001];
int A[31],B[31];
int uesd[31];
int used[31];
int inline min(int a,int b){return a<b?a:b;}
int main(){
freopen("job.in","r",stdin);
freopen("job.out","w",stdout);
int n,a,b;
int min,minl;
scanf("%d %d %d",&n,&a,&b);
for(int i=1;i<=a;i++){
scanf("%d",&A[i]);
uesd[i]=A[i];
}
for(int i=1;i<=b;i++){
scanf("%d",&B[i]);
used[i]=B[i];
}
for(int i=1;i<=n;i++){
min=uesd[1];
minl=1;
for(int k=2;k<=a;k++)
if(uesd[k]<min){
minl=k;
min=uesd[k];
}
timea[i]=uesd[minl];
uesd[minl]+=A[minl];
}
for(int i=1;i<=n;i++){
min=used[1];
minl=1;
for(int k=2;k<=b;k++)
if(used[k]<min){
minl=k;
min=used[k];
}
timeb[i]=used[minl];
used[minl]+=B[minl];
}
min=0;
for(int i=1;i<=n;i++)
if(min<timea[i])//这里是max
min=timea[i];
printf("%d ",min);
min=0;
for(int i=1;i<=n;i++)
if(min<timea[i]+timeb[n-i+1])//这里是max
min=timea[i]+timeb[n-i+1];
printf("%d\n",min);
fclose(stdin);
fclose(stdout);
return 0;
}
证明什么的超出了本人水平,略去。