小弟在五一期间每天会发一个宫的题,给各位大哥解解闷,顺便结识一些对算法感兴趣的朋友.望大家都能闯过十二宫.大家闯宫成功后请把答案写在回复中,以便让大家分享.Background
话说星矢、紫龙、冰河、阿瞬为了救活雅典娜，必须勇闯黄金十二宫。 Problem
首先他们来到了白羊宫，身为白羊座黄金圣斗士的穆先生，早就知道假教皇的阴谋，于是他决定帮助星矢他们。穆先生发现，他们四人经过数次大战，身上的圣衣已经有多处破损，如果继续去挑战黄金圣斗士，一定会输的。便要帮星矢等人修补他们的圣衣。 现在已知四人圣衣有几处破损(s1,s2,s3,s4)，而且每处破损程度不同，破损程度越厉害，穆先生就需要更多时间来修好它。破损程度用穆先生需修好它用的时间表示(A1到As1,B1到Bs2,C1到Cs3,D1到Ds4)。不过穆先生能力很强，可以同时修补2处破损。但是这2处破损，只能是同一件圣衣上的。就是说他只能同时修补一件圣衣，修好了，才能修补下一件。 Input
本题包含多组数据，每组数据5行. 第1行，为s1,s2,s3,s4(1<=s1,s2,s3,s4<=20) 第2行，为A1...As1 共s1个数，表示第一件圣衣上每个破损处的程度，也就是穆先生修好它所用的时间.第3行，为B1...Bs2 共s2个数，表示第二件圣衣上每个破损处的程度，也就是穆先生修好它所用的时间.第4行，为C1...Cs3 共s3个数，表示第三件圣衣上每个破损处的程度，也就是穆先生修好它所用的时间.第5行，为D1...Ds4 共s4个数，表示第四件圣衣上每个破损处的程度，也就是穆先生修好它所用的时间 (1<=A1...As1,B1...Bs2,C1...Cs3,D1...Ds4<=60) Output
对于每组数据输出一行，为穆先生修好四件圣衣所要的最短时间。(对Sample output的说明：5＋4＋6＋(2＋3)＝20) Sample Input
1 2 1 3
5
4 3
6
2 4 3Sample Output
20
话说星矢、紫龙、冰河、阿瞬为了救活雅典娜，必须勇闯黄金十二宫。 Problem
首先他们来到了白羊宫，身为白羊座黄金圣斗士的穆先生，早就知道假教皇的阴谋，于是他决定帮助星矢他们。穆先生发现，他们四人经过数次大战，身上的圣衣已经有多处破损，如果继续去挑战黄金圣斗士，一定会输的。便要帮星矢等人修补他们的圣衣。 现在已知四人圣衣有几处破损(s1,s2,s3,s4)，而且每处破损程度不同，破损程度越厉害，穆先生就需要更多时间来修好它。破损程度用穆先生需修好它用的时间表示(A1到As1,B1到Bs2,C1到Cs3,D1到Ds4)。不过穆先生能力很强，可以同时修补2处破损。但是这2处破损，只能是同一件圣衣上的。就是说他只能同时修补一件圣衣，修好了，才能修补下一件。 Input
本题包含多组数据，每组数据5行. 第1行，为s1,s2,s3,s4(1<=s1,s2,s3,s4<=20) 第2行，为A1...As1 共s1个数，表示第一件圣衣上每个破损处的程度，也就是穆先生修好它所用的时间.第3行，为B1...Bs2 共s2个数，表示第二件圣衣上每个破损处的程度，也就是穆先生修好它所用的时间.第4行，为C1...Cs3 共s3个数，表示第三件圣衣上每个破损处的程度，也就是穆先生修好它所用的时间.第5行，为D1...Ds4 共s4个数，表示第四件圣衣上每个破损处的程度，也就是穆先生修好它所用的时间 (1<=A1...As1,B1...Bs2,C1...Cs3,D1...Ds4<=60) Output
对于每组数据输出一行，为穆先生修好四件圣衣所要的最短时间。(对Sample output的说明：5＋4＋6＋(2＋3)＝20) Sample Input
1 2 1 3
5
4 3
6
2 4 3Sample Output
20
由于同时只能修理一件，所以整体最佳方案中每件的修理都是最佳方案。
以下只讨论一件的修理方案。1、将破损程度从大到小排序
2、设置两个变量X、Y和两个数组AX和AY。初始值为0
3、循环从排好序的数组中顺序取出数字z（破损程度）来，如果X<Y则x=x+z同时将z插入AX，否则y=y+z同时将z插入AY。
4、从两个数组中各取出一个修理，修理完一处后从完成那一处所在的数组中取下一个修理。直至都修理完。证明：
1、存在最佳的修理方式即AX和AY，其中AX中最小值为A，AY中为B。设A<B
2、那么有AX的和>=AY的和，否则的话A、B互换所在的数组之后构成的方式是最佳方式，和前提AX和AY是最佳方式矛盾。
3、从原数组和AX中去掉A，这时为去掉A的最佳方案。利用归纳法重复第一步。到AX或AY中只有一个的时候自然也是最佳方案。
hours before the holiday seems always longer than a whole day.
Windows sucks! Cann't type chinese now!
1 2 1 3：max(3+1,1+2)=4
5:5
4 3:max(3,4)=4
6:6
2 4 3:max(4,2+3)=5
总共24啊
第一行是每件圣衣有几处破损，如1 2 1 3表示第一件有1处破损，第二件有2处，第三件有1处，第四件有3处。
希望你再接再厉。突破十二宫 ：）
我的QQ：285931179
关键错在这步，为什么从AX中去掉A后，仍然为最佳方案呢，哪里证明了？
以下讨论的是一件衣服。
正确的解法应该是把所有的数加起来得到a
b等于a/2（向下取整，向上也可）
要从所有的数中找一些加起来最靠近b。典型的背包问题。想岔了啊！
正确的解法应该是把所有的数加起来得到a
if(a%2==0)b=a/2;
else b=a/2+1;
不知道这样对不对，感觉应该差不多。
sum=0
就是 每次选出两个最大的，然后都减一，sum++。
然后把这两个数重新放放回（如果刚才的减一导致变成0，则丢弃这个数），然后再选出两个最大的，重复上面的操作。。
注：如果不能选出两个的时候，就选一个。
原数据：5 5 4 4 3
最佳是 5 5, 4 4 3
顺便说明下我在上面写的想法
1、找到最接近总和的一半的整数。例如总数为2*n+1，那么n和n+1均可。
2、转化为求解容量为n或n+1，物品重量为原来那些数据的背包问题。
假设我们选了n，最佳解为x,y，那么总有一个小于等于n。如果两个都大于等于n则总和为2*n+2。
所以选n和n+1是没关系的，确定了一组值，另外一组也自然确定。
因为修每件衣服为最优的，那么总结果是最优的。
所以我只考虑单件衣服如何取得最优：就是 每次选出两个最大的，然后都减一，sum++。
然后把这两个数重新放放回（如果刚才的减一导致变成0，则丢弃这个数），然后再选出两个最大的，重复上面的操作。。
注：如果不能选出两个的时候，就选一个。你说的反例：
反例:
原数据：5 5 4 4 3
最佳是 5 5, 4 4 3这个在我这里也是正确的阿
1 2 1 3
5
4 3
6
2 4 3Sample Output
20根据同时补两处的原则：
max(5)=5
max(4,3)=4,
max(6)=6
max(4,3)+max(2)=6
应该是：21呀
真牛，我们怎么没有想到一件衣服还没修完就能换别的衣服修呢？