若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

2362: 愚公的遗愿

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,483

题目描述

愚公留下遗愿,让他的两个儿子愚大和愚二完成他移山的愿望:将石头搬出大山。一直以来,愚大背大石头,将小石头留给弟弟愚二背。愚二长大后,想分担哥哥的负担,要求背大石头,让哥哥背小石头。愚大不同意。兄弟二人多次讨论,也不能提出一个公平背石头的方案。
假设有n 块石头,将这n个石头尽可能平分给兄弟二人,即两人分得的石头重量差异最小。请你帮助愚家兄弟解决这个问题。

输入

多组输入,对于每组数据
第一行,一个整数n(3<=n<=1000),表示石头的数目
第二行,n个整数,对于每个整数a[i](1<=a[i]<=50),表示第i块石头的重量

输出

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

样例输入

3
1 2 3

样例输出

3 3

参考代码

#include<stdio.h>
#include<string.h>
int main() 
{
    int n,a[1001],v[100000]={0},sum,k,i,j;
    while(scanf("%d",&n)!=EOF) 
    {
        sum=0;
        for (i=0;i<n;i++) 
        {
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        k=sum/2;
        for (i=0;i<n;i++)
                    for (j=k;j>=a[i];j--) 
        {
            if(a[i]+v[j-a[i]]>v[j])
                                v[j]=a[i]+v[j-a[i]];
        }
        printf("%d %dn",v[k],sum-v[k]);
    }
    return 0;
}

解析

暂无

hustoj

发表评论 取消回复

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

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Skip Dreams孤独患者 原站点
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist