Problem C: Celebrity Split

Problem C: Celebrity Split

时间: 120ms        内存:128M

描述:

Problem C: 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.

Example

Suppose Jack and Jill own 5 mansions valued at 6,000,000, 30,000,000, 3,000,000, 11,000,000, and 3,000,000 dollars. To satisfy their requirements, Jack or Jill would receive the mansion worth 6,000,000 and the other would receive both manstions worth 3,000,000 dollars. The mansions worth 11,000,000 and 30,000,000 dollars would be sold, for a total of 41,000,000 dollars. The answer is therefore 41000000.

输入:

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 24. 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.

输出:

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.

示例输入:

5
6000000
30000000
3000000
11000000
3000000
0

示例输出:

41000000

提示:

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

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 100;

int lis[MAXN], n, bes, sum[MAXN];

void search(int p, int dif, int s) {
  if(dif == 0 && s > bes) {
    bes = s;
//printf("%d\n", sum[n-1] - bes);
  }
  if(p >= 0) {
    if(abs(dif) > sum[p]) return;
    if(s + sum[p] <= bes) return;
    search(p - 1, dif + lis[p], s + lis[p]); 
    search(p - 1, dif - lis[p], s + lis[p]); 
    search(p - 1, dif, s);
  }
}

int Split(int N, int *M){
  n = N;
  for(int i = 0; i < n; ++i) {
    lis[i] = M[i];
    sum[i] = ((i == 0) ? 0 : sum[i-1]) + lis[i];
  }
  bes = 0;
  search(n-1, 0, 0);
//printf("%d\n", sum[n-1] - bes);
  return sum[n-1] - bes;
}

main() {
    int N;
    int M[33];
    int i;
    while(1) {
        scanf("%d", &N);
        if(!N) break;
        for(i = 0; i < N; i++) scanf("%d", M+i);
        i = Split(N,M);
        printf("%d\n", i);
    }
}

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

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int RNG = 100;
const int ZERO = 50;

int dir[8][2] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
{1, -2}, {1, 2}, {2, -1}, {2, 1}};

int d[RNG][RNG];
int q[RNG*RNG][2], tail;

void add(int r1, int c1, int d1) {
  if(d[r1][c1] == -1) {
    d[r1][c1] = d1;
    q[tail][0] = r1; 
    q[tail++][1] = c1;
  }
}

int moo(int x, int y) {
  x = abs(x);
  y = abs(y);
  if(x < y) swap(x, y);
  if(x < 20 && y < 20) return d[ZERO + x][ZERO + y];
  if(y == 0) {
    int k = max(0, (x - 10) / 4);
    return k * 2 + moo(x - k * 4, 0);
  }
  else if(x < y + 3) {
    int k = max(0, (y - 10) / 3);
    return k * 2 + moo(x - k * 3, y - k * 3);
  }
  else {
    int k = min(min(x - y, y), max(x / 2, y) - 5);
    return k + moo(x - k * 2, y - k);
  } 
}

char line[1234];
int main() {
  for(int i = 0; i < RNG; ++i)
    for(int j = 0; j < RNG; ++j)
      d[i][j] = -1;
  tail = 0;
  add(ZERO, ZERO, 0);
  for(int i = 0; i < tail; ++i)
    for(int j = 0; j < 8; ++j)
      add(q[i][0] + dir[j][0], q[i][1] + dir[j][1], d[q[i][0]][q[i][1]] + 1); 
  gets(line);
  while(strcmp(line, "END") != 0) {
    int x, y;
    sscanf(line, "%d%d", &x, &y);
    printf("%d\n", moo(x, y));
    gets(line);
  }
  return 0;
}

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

点赞

发表评论

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