2015
04-10

# Celebrity Split

Jack and Jill have decided to separate and divide their property equally. Each of their N mansions has a value between 1,000,000 and 40,000,000 dollars. Jack will receive some of the mansions; Jill will receive some of the mansions; the remaining mansions will be sold, and the proceeds split equally.

Neither Jack nor Jill can tolerate the other receiving property with higher total value. The sum of the values of the mansions Jack receives must be equal to the sum of the values of the mansions Jill receives. So long as the value that each receives is equal, Jack and Jill would like each to receive property of the highest possible value.

Given the values of N mansions, compute the value of the mansions that must be sold so that the rest may be divided so as to satisfy Jack and Jill.

The input consists of a sequence of test cases. The first line of each test case contains a single integer N, the number of mansions, which will be no more than 20. This line is followed by N lines, each giving the value of a mansion. The final line of input contains the integer zero. This line is not a test case and should not be processed.

The input consists of a sequence of test cases. The first line of each test case contains a single integer N, the number of mansions, which will be no more than 20. This line is followed by N lines, each giving the value of a mansion. The final line of input contains the integer zero. This line is not a test case and should not be processed.

5
6000000
30000000
3000000
11000000
3000000
0

41000000

< [if gte mso 9]>MicrosoftInternetExplorer402DocumentNotSpecified7.8Normal0

Hdu 3765
Celebrity Split

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 18    Accepted Submission(s): 16

Problem Description

Jack and Jill have decided to separate and divide their property equally. Each of their N mansions has a value between 1,000,000 and 40,000,000 dollars. Jack will receive some of the mansions; Jill will receive some of the mansions; the remaining mansions will be sold, and the proceeds split equally.

Neither Jack nor Jill can tolerate the other receiving property with higher total value. The sum of the values of the mansions Jack receives must be equal to the sum of the values of the mansions Jill receives. So long as the value that each receives is equal, Jack and Jill would like each to receive property of the highest possible value.

Given the values of N mansions, compute the value of the mansions that must be sold so that the rest may be divided so as to satisfy Jack and Jill.

Input

The input consists of a sequence of test cases. The first line of each test case contains a single integer N, the number of mansions, which will be no more than 20. This line is followed by N lines, each giving the value of a mansion. The final line of input contains the integer zero. This line is not a test case and should not be processed.

Output

For each test case, output a line containing a single integer, the value of the mansions that must be sold so that the rest may be divided so as to satisfy Jack and Jill.

Sample Input

6000000 30000000 3000000 11000000 3000000 0

Sample Output

41000000

Jill

N<=20

20

B

N=20的时候其实如果枚举是可以解决的。

，要么给
Jill
，要么拍卖，所以可以递归求解。

#include <stdio.h>
#include <math.h>
int a[200];
int n;
int ans;
int sum[200];
void Divide(int p,int differ,int hav)//p为现在要拿的房子，differ为目前两个人房子价值的差距，hav为两个人共拿走的价值
{
int i,j,n;
if (differ==0)
{
if (hav>ans) ans=hav;
}
if (p<0) return;
if (abs(differ)>sum[p]) return;//剪枝1：如果两个人拿到的差距比剩下的所有房子之和大，返回。
if (sum[p]+hav<ans) return;//剪枝2：如果剩下的都加上还不能加到目前最大的答案ans，返回。
Divide(p-1,differ+a[p],hav+a[p]);//给其中一个人
Divide(p-1,differ-a[p],hav+a[p]);//给另一个人
Divide(p-1,differ,hav);//拿去拍卖
}
int Solve()
{
ans=0;
Divide(n-1,0,0);
return sum[n-1]-ans;
}
int main()
{
int i,j;
while(1)
{
scanf("%d",&n);
if (n==0) break;
for (i=0;i<n;i++)
{
scanf("%d",&a[i]);
if (i==0) sum[i]=a[i];
else sum[i]=sum[i-1]+a[i];
}
printf("%d/n",Solve());
}
return 0;
}



1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

2. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}