如果我读题没错的话,
本题核心就是将若干数分两组,使两组数的差的绝对值最小
所以很自然想到贪心
我们声明一个v表示差值,将数据排序从大到小考虑,若v不大于0,则v加上该数,否则v减去该数
最后将v取绝对值,总时间减v再除以二,最后加v 即为该科最短时间
然而交上去全wa。。并且没数据。。。。
思路有问题的话望指正,谢谢辣
有hack也行
代码
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int s[4],t[200];
int cmp(int a,int b){return b<a;}
int cal(int n){
int i=0,v=0,cnt=0;
while(i<n){
cnt+=t[i];
if(v<=0)v+=t[i];
else v-=t[i];
i++;
}
v=abs(v);
return (cnt-v)/2+v;
}
int ans;
int main(){
for(int i=0;i<4;i++){cin>>s[i];}
for(int i=0;i<4;i++){
for(int j=0;j<s[i];j++){
cin>>t[j];
}
sort(t,t+s[i],cmp);
ans+=cal(s[i]);
}
cout<<ans;
return 0;
}