果斷貪心第一問：
第一問代碼
/*
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;
}
仔細(xì)想了一下第二問也應(yīng)該是貪心，但感覺在第一問的基礎(chǔ)上做無從下手。
其實(shí)第一問的代碼是以機(jī)器為單位來求最長時(shí)間的，對于第二問就無法照搬了。
但其實(shí)可以以每個(gè)產(chǎn)品為單位，計(jì)算出第i個(gè)加工好的產(chǎn)品所需時(shí)間。
a中最早的產(chǎn)品，作為b中所花時(shí)間最多的產(chǎn)品來加工，這樣保證結(jié)果最優(yōu)。
搞笑的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;
}
證明什么的超出了本人水平，略去。