我的策略是优先选择时长最长的两个来做,每一次都是这样,但是只得到60分,我实在是想不出一个例子能够推翻我的代码,还请有空的大佬帮忙看看
下面是代码,几乎每一行都有注释
#include<bits/stdc++.h>
#include <windows.h>
using namespace std;
int s1,s2,s3,s4,ax,bx,cx,dx;
int a[61],b[61],c[61],d[61];
int ans;
int calc(int* a,int mx){
int sum=0;
int nt=0;
for(int t=mx;t>=1;){//先挑出时间最长的作业开始做
if(a[t]){//确保有时长为t的作业
if(a[t]>1){//时长为t的作业不止一个,可以一起做两个
sum+=(a[t]/2)*t;
a[t]=(a[t]%2);
}else{
nt=t-1;
while(nt>0&&(!a[nt])){//找出下一个能够同时一起做的作业
nt--;
}
if(nt>0){//还有可以一起做的作业
sum+=nt;
a[t-nt]++;//把时长为t的作业转化为了时长为n-nt的作业
a[t]=0; //时长为t的作业做完了
a[nt]--;//时长为nt的做完一个
if(t-nt>nt){
t=t-nt;//产生一个时长比nt还要长的作业如:1 8 20
}else{
t=nt;
}
}else{//已经没有作业和时长为t的作业一起做了
sum+=t;
break;
}
}
}else{
t--;//继续找下一个时长大的题先来做如 4 3
}
}
return sum;
}
int main(){
cin>>s1>>s2>>s3>>s4;
int temp;
for(int i=1;i<=s1;i++){
cin>>temp;
a[temp]++;
ax=max(ax,temp);
}
for(int i=1;i<=s2;i++){
cin>>temp;
b[temp]++;
bx=max(bx,temp);
}
for(int i=1;i<=s3;i++){
cin>>temp;
c[temp]++;
cx=max(cx,temp);
}
for(int i=1;i<=s4;i++){
cin>>temp;
d[temp]++;
dx=max(dx,temp);
}
cout<<calc(a,ax)+calc(b,bx)+calc(c,cx)+calc(d,dx);
return 0;
}