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
98
99
100
101
102
103
104
|
// 2561. Rearranging Fruits
#include "leetcode.h"
/*
* you have two fruit baskests containing 'n' fruits each. you are given two
* indexed integer arrays 'basket1' and 'basket2' representing the cost of fruit
* in each baset. you want o make both baskets equal. to do so, you can use the
* following operation as many times as you want: chose two indices 'i' and 'j'
* and swap the i'th fruit of 'basket1' with the j'th fruit of 'basket2'. the
* cost of the swap is 'min(basket1[i], basket2[j])'. two baskets are considered
* equal if sorting them according to the fruit cost makes them exactly the same
* baksets. return the minimum cost to make both baskets equal or -1 if
* impossible.
*/
struct map_entry {
int key;
int val;
};
struct map {
struct map_entry *entries;
int size;
int capacity;
};
void map_init(struct map *obj) {
obj->capacity = 16;
obj->size = 0;
obj->entries =
(struct map_entry *)malloc(obj->capacity * sizeof(struct map_entry));
}
void map_insert(struct map *obj, int key, int delta) {
for (int i = 0; i < obj->size; i++)
if (obj->entries[i].key == key) {
obj->entries[i].val += delta;
return;
}
if (obj->size == obj->capacity) {
obj->capacity *= 2;
obj->entries = (struct map_entry *)realloc(
obj->entries, obj->capacity * sizeof(struct map_entry));
}
obj->entries[obj->size].key = key;
obj->entries[obj->size].val = delta;
obj->size++;
}
int cmp(const void *a, const void *b) {
struct map_entry *aa = (struct map_entry *)a;
struct map_entry *bb = (struct map_entry *)b;
return aa->key - bb->key;
}
void map_sort(struct map *obj) {
qsort(obj->entries, obj->size, sizeof(struct map_entry), cmp);
}
long long minCost(int *basket1, int basket1Size, int *basket2,
int basket2Size) {
long long ans = 0;
struct map map;
map_init(&map);
for (int i = 0; i < basket1Size; i++) {
map_insert(&map, basket1[i], 1);
map_insert(&map, basket2[i], -1);
}
map_sort(&map);
if (!map.size)
return 0;
int m = map.entries[0].key;
int *arr = NULL, arr_size = 0, arr_capacity = 0;
for (int i = 0; i < map.size; i++) {
int val = map.entries[i].key, key = map.entries[i].val;
if (key % 2) {
free(map.entries);
if (arr)
free(arr);
return -1;
}
int cnt = abs(key) / 2;
for (int j = 0; j < cnt; j++) {
if (arr_size == arr_capacity) {
arr_capacity = !arr_capacity ? 1 : arr_capacity * 2;
arr = (int *)realloc(arr, arr_capacity * sizeof(int));
}
arr[arr_size++] = val;
}
}
for (int i = 0; i < arr_size / 2; i++)
ans += (arr[i] < 2 * m) ? arr[i] : 2 * m;
free(map.entries), free(arr);
return ans;
}
int main() {
int b11[] = {4, 2, 2, 2}, b21[] = {1, 4, 1, 2};
int b12[] = {2, 3, 4, 1}, b22[] = {3, 2, 5, 1};
printf("%lld\n",
minCost(b11, ARRAY_SIZE(b11), b21, ARRAY_SIZE(b21))); // expect: 1
printf("%lld\n",
minCost(b12, ARRAY_SIZE(b12), b22, ARRAY_SIZE(b22))); // expect: -1
}
|