主题:大虾 请进
宿舍楼决定举行CounterStrike游戏大赛,为了使比赛更为精彩,大家决定将所有参赛同学先平均分为东西部两大联盟再组队对战,根据之前比赛的统计,每个同学的游戏战斗力分别为S1,S2,S3...SN.(S<=100000)。现在需要你将参赛同学平均分到两大联盟中,使得两联盟的总战斗力的差为最小,以增加比赛的激烈性。要注意的是两联盟的人数不一定相同,比如一个战斗力90000的同学能够以一敌十。
该程序有多组测试数据,每组测试数据第一行为整数N(1<=N<=20),表示有N个同学。接下去N行,为每个同学的战斗力。
每组测试数据只需输出经过划分后两联盟的总战斗力差的最小值。
我的算法是
#include<iostream>
#include<string.h>
#include<cmath>
long bag[1000010];
using namespace std;
int main()
{
long count[21];
long s,sum,total;
int i,j,n;
while(cin>>n)
{memset(bag,0,sizeof(bag));
memset(count,0,sizeof(count));
s=0;
sum=0;
for(i=1;i<=n;i++)
{cin>>count[i];
sum+=count[i];
}
total=sum/2;
for(i=1;i<=n;i++)
for(j=total;j>=count[i];j--)
if(bag[j]<bag[j-count[i]]+count[i])
bag[j]=bag[j-count[i]]+count[i];
for(i=total;i>=1;i--)
if(bag[i]) break;
s=abs(sum-bag[i]*2);
cout<<s<<endl;
}
return 0;
}
请问大虾 有更好的代码吗
该程序有多组测试数据,每组测试数据第一行为整数N(1<=N<=20),表示有N个同学。接下去N行,为每个同学的战斗力。
每组测试数据只需输出经过划分后两联盟的总战斗力差的最小值。
我的算法是
#include<iostream>
#include<string.h>
#include<cmath>
long bag[1000010];
using namespace std;
int main()
{
long count[21];
long s,sum,total;
int i,j,n;
while(cin>>n)
{memset(bag,0,sizeof(bag));
memset(count,0,sizeof(count));
s=0;
sum=0;
for(i=1;i<=n;i++)
{cin>>count[i];
sum+=count[i];
}
total=sum/2;
for(i=1;i<=n;i++)
for(j=total;j>=count[i];j--)
if(bag[j]<bag[j-count[i]]+count[i])
bag[j]=bag[j-count[i]]+count[i];
for(i=total;i>=1;i--)
if(bag[i]) break;
s=abs(sum-bag[i]*2);
cout<<s<<endl;
}
return 0;
}
请问大虾 有更好的代码吗