2011-10-29 07:00:36Morris
a276. 又分糖果囉
a276. 又分糖果囉
/**********************************************************************************/
/* Problem: a276 "又分糖果囉" from */
/* Language: C (1187 Bytes) */
/* Result: AC(256ms, 6.4MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-28 18:45:40 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define mod 100000
int HASH[mod], size;
struct Node {
int v, next;
}Node[1049000];
int insHASH(int v) {
static int m;
m = v%mod;
int pre = 0, now = HASH[m];
while(now) {
if(Node[now].v < v)
pre = now, now = Node[now].next;
else if(Node[now].v == v)
return 0;
else
break;
}
size++;
if(!pre) HASH[m] = size;
else Node[pre].next = size;
Node[size].v = v;
Node[size].next = now;
return 1;
}
int freeHASH() {
memset(HASH, 0, sizeof(HASH));
}
int cmp(const void *i, const void *j) {
return *(int *)j - *(int *)i;
}
int DP[1049000];
int main() {
int n, A[20], i, j, Dt, tmp;
while(scanf("%d", &n) == 1) {
freeHASH();
int sum = 0, max = 0, before;
for(i = 0; i < n; i++)
scanf("%d", &A[i]), sum += A[i];
qsort(A, n, sizeof(int), cmp);
Dt = 0, DP[0] = 0, tmp = sum/2, size = 0;
for(i = 0; i < n; i++) {
for(j = 0, before = Dt; j <= before; j++) {
if(A[i]+DP[j] <= tmp) {
if(insHASH(A[i]+DP[j])) DP[++Dt] = A[i]+DP[j];
max = max > A[i]+DP[j] ? max : A[i]+DP[j];
}
}
}
printf("%d\n", sum-2*max);
}
return 0;
}
內容 ：
再分糖果吧！
你一開始有 n 包糖果，每包糖果裡面有若干顆，想要公平的分給 2 個人
所謂公平就是指這兩個人有的糖果數量的差越小越好。
輸入說明
：
多組輸入，以EOF作為結束
每組測試資料的第一行是一個正整數 n ，第二行有 n 個數字 mi 以空格隔開
1<= n <=20
1<=mi <=1000000
輸出說明
：
輸出兩人糖果數量的的差。
範例輸入 ：
4 1 3 7 8 5 1 2 4 9 4
範例輸出 ：
1 0
提示
：
第一組：(3,7) 和 (1,8)
第二組：(4,4,2) 和 (1,9)
出處
：
/**********************************************************************************/
/* Problem: a276 "又分糖果囉" from */
/* Language: C (1187 Bytes) */
/* Result: AC(256ms, 6.4MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-28 18:45:40 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define mod 100000
int HASH[mod], size;
struct Node {
int v, next;
}Node[1049000];
int insHASH(int v) {
static int m;
m = v%mod;
int pre = 0, now = HASH[m];
while(now) {
if(Node[now].v < v)
pre = now, now = Node[now].next;
else if(Node[now].v == v)
return 0;
else
break;
}
size++;
if(!pre) HASH[m] = size;
else Node[pre].next = size;
Node[size].v = v;
Node[size].next = now;
return 1;
}
int freeHASH() {
memset(HASH, 0, sizeof(HASH));
}
int cmp(const void *i, const void *j) {
return *(int *)j - *(int *)i;
}
int DP[1049000];
int main() {
int n, A[20], i, j, Dt, tmp;
while(scanf("%d", &n) == 1) {
freeHASH();
int sum = 0, max = 0, before;
for(i = 0; i < n; i++)
scanf("%d", &A[i]), sum += A[i];
qsort(A, n, sizeof(int), cmp);
Dt = 0, DP[0] = 0, tmp = sum/2, size = 0;
for(i = 0; i < n; i++) {
for(j = 0, before = Dt; j <= before; j++) {
if(A[i]+DP[j] <= tmp) {
if(insHASH(A[i]+DP[j])) DP[++Dt] = A[i]+DP[j];
max = max > A[i]+DP[j] ? max : A[i]+DP[j];
}
}
}
printf("%d\n", sum-2*max);
}
return 0;
}