aboutsummaryrefslogtreecommitdiff
path: root/rearranging_fruits.c
blob: 4252d05f7476f3bec4a3997294a0aacc095cb428 (plain)
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
}