愚公的遗愿

愚公的遗愿

时间: 1ms        内存:64M

描述:

愚公留下遗愿,让他的两个儿子愚大和愚二完成他移山的愿望:将石头搬出大山。一直以来,愚大背大石头,将小石头留给弟弟愚二背。愚二长大后,想分担哥哥的负担,要求背大石头,让哥哥背小石头。愚大不同意。兄弟二人多次讨论,也不能提出一个公平背石头的方案。

假设有n 块石头,将这n个石头尽可能平分给兄弟二人,即两人分得的石头重量差异最小。请你帮助愚家兄弟解决这个问题。

输入:

多组输入,对于每组数据

第一行,一个整数n(3<=n<=1000),表示石头的数目

第二行,n个整数,对于每个整数a[i](1<=a[i]<=50),表示第i块石头的重量

输出:

对于每组输入输出两个数 x,y(x<=y) 分别表示两个兄弟背的石头总重量

示例输入:

3
1 2 3

示例输出:

3 3

提示:

参考答案(内存最优[1000]):

#include<stdio.h>
#include<string.h>

#define LL long long
#define max(a,b) a>b? a:b


int num[1010];
int f[50000];

int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        int sum=0;

        for(int i=0;i<n;i++){
            scanf("%d",&num[i]);
            sum+=num[i];
        }
        memset(f,0,sizeof(f));

        int s=sum/2;

        for(int i=0;i<n;i++)
            for(int j=s;j>=num[i];j--)
                f[j]=max(f[j],f[j-num[i]]+num[i]);
        printf("%d %d\n",f[s],sum-f[s]);

    }

    return 0;
}

参考答案(时间最优[0]):

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
int a[1005];
int n;
int main()
{
	while(~scanf("%d",&n))
	{
		int sum=0,mins;
		for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		sum+=a[i];
	}
	mins=sum;
	sort(a,a+n);
	int t=0,k=0,n1,n2;
	for(int i=0;i<n;i++)
	   if(t<sum/2)
	   {
	   	t+=a[i];
	   	k++;
	   }
	   else break; 
	 if(sum%2==0&&t==sum/2)
	 printf("%d %d\n",t,t);
	 else
	 {
	 	int temp=sum-t;
	 	n1=temp;
	 	n2=t;
	 	mins=fabs(t-temp);
	 	for(int j=0;j<k;j++)
	 	{
	 		int x=temp+a[j];
	 		int y=t-a[j];
	 		if(fabs(x-y)<mins)
	 		{
	 			mins=fabs(x-y);
	 			n1=x;n2=y;
			}
		}
		if(n1>n2)
		 printf("%d %d\n",n2,n1);
		else printf("%d %d\n",n1,n2);
	 }
	}
	
	return 0;
} 

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注