-
Notifications
You must be signed in to change notification settings - Fork 0
/
greedy.c
97 lines (91 loc) · 2.76 KB
/
greedy.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <stdio.h>
#include <stdlib.h>
typedef struct setnode setnode_t;
struct setnode {
setnode_t *next;
long long item_val;
};
typedef struct setlist setlist_t;
struct setlist {
setnode_t *head;
long long sum;
};
setlist_t *setlist_malloc(void);
void setlist_push(setlist_t *sl, long long item_val);
void setlist_free(setlist_t *sl);
void setlist_print(const setlist_t *sl);
typedef struct llarray llarray_t;
struct llarray {
size_t count;
long long *elems;
};
int llong_dsc_cmp(const void *a, const void *b);
int main(void) {
llarray_t items;
scanf(" %zu", &items.count);
items.elems = malloc(items.count*sizeof(*items.elems));
for (size_t i=0; i<items.count; i++) {
scanf(" %lld", items.elems+i);
}
qsort(items.elems, items.count, sizeof(*items.elems), llong_dsc_cmp);
setlist_t *set0 = setlist_malloc();
setlist_t *set1 = setlist_malloc();
for (size_t i=0; i<items.count; i++) {
if (set0->sum <= set1->sum) {
setlist_push(set0, items.elems[i]);
} else {
setlist_push(set1, items.elems[i]);
}
}
printf("set0:\n");
setlist_print(set0);
printf("set1:\n");
setlist_print(set1);
printf("sum diff = %lld\n", (set0->sum < set1->sum)
? set1->sum - set0->sum
: set0->sum - set1->sum);
setlist_free(set0);
setlist_free(set1);
free(items.elems);
return 0;
}
setlist_t *setlist_malloc(void) {
setlist_t *tmp = malloc(sizeof(*tmp));
tmp->head = NULL;
tmp->sum = 0;
return tmp;
}
void setlist_push(setlist_t *sl, long long item_val) {
setnode_t *next = sl->head;
sl->head = malloc(sizeof(*sl->head));
sl->head->next = next;
sl->head->item_val = item_val;
sl->sum += item_val;
}
void setlist_free(setlist_t *sl) {
setnode_t tmp;
tmp.next = sl->head;
while (tmp.next != NULL) {
setnode_t *next = tmp.next->next;
free(tmp.next);
tmp.next = next;
}
free(sl);
}
void setlist_print(const setlist_t *sl) {
printf("set sum: %lld\n"
"set items:\n",
sl->sum);
setnode_t tmp;
tmp.next = sl->head;
while (tmp.next != NULL) {
printf("%lld ", tmp.next->item_val);
tmp.next = tmp.next->next;
}
putchar('\n');
}
int llong_dsc_cmp(const void *a, const void *b) {
long long av = *(long long *)a;
long long bv = *(long long *)b;
return (av > bv)*(-1) + (av < bv)*(1);
}