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
105
106
107
108
109
110
111
|
// 857. Minimum Cost to Hire K Workers
#include "leetcode.h"
/*
* there are 'n' workers. you are given two integer arrays 'quality' and 'wage'
* where 'quality[i]' is the quality of the i'th worker and 'wage[i]' is the
* minimum wage expectation for the i'th worker. we want to hire exactly 'k'
* workers to form a paid group. to hire a group of 'k' workers, we must pay
* them according to the following rules. every worker in the paid group must be
* paid at least their minimum wage expectation. in the group, each worker's pay
* must be directly proportional to their quality. this means if a worker's
* quality is double that of another worker in the group, then they must be paid
* twice as much as the other worker. given the integer 'k', return the least
* amount of money needed to form apaid group satisfying the above conditions.
*/
struct workers {
int q;
int w;
double w_p_q;
};
int cmp_work(const void *a, const void *b) {
double tmp = ((struct workers *)b)->w_p_q - ((struct workers *)a)->w_p_q;
if (tmp < 0)
return -1;
return 1;
}
int cmp(const void *a, const void *b) { return *(int *)b - *(int *)a; }
void max_heap_insert(int *heap, int *n, int val) {
int i = ++(*n), parent = i / 2;
while (i != 1 && val > heap[parent]) {
heap[i] = heap[parent];
i = parent;
parent /= 2;
}
heap[i] = val;
}
int max_heap_delete(int *heap, int *n) {
int val = heap[1], tmp = heap[*n--], parent = 1, child = parent * 2;
while (child <= *n) {
if (child < *n && heap[child] < heap[child + 1])
child++;
if (tmp >= heap[child])
break;
else {
heap[parent] = heap[child];
parent = child;
child *= 2;
}
}
heap[parent] = tmp;
return val;
}
void get_dp(struct workers *arr, int size, int num, int *dp) {
if (!num)
return;
int tmp[num + 1], n = 0, sum = 0;
for (int i = size - num; i < size; i++) {
max_heap_insert(tmp, &n, arr[i].q);
sum += arr[i].q;
}
dp[size - num] = sum;
for (int i = size - num - 1; i >= 0; i--) {
if (arr[i].q < tmp[1]) {
sum -= max_heap_delete(tmp, &n);
sum += arr[i].q;
max_heap_insert(tmp, &n, arr[i].q);
}
dp[i] = sum;
}
}
double mincostToHireWorkers(int *quality, int qualitySize, int *wage,
int wageSize, int k) {
if (qualitySize == 1)
return wage[0];
struct workers *member =
(struct workers *)malloc(qualitySize * sizeof(struct workers));
for (int i = 0; i < qualitySize; i++) {
member[i].q = quality[i];
member[i].w = wage[i];
member[i].w_p_q = (double)wage[i] / quality[i];
}
double ans = 1000000000, cost;
int max = 0x7fffffff, q_idx = 0, dp[qualitySize];
qsort(member, qualitySize, sizeof(struct workers), cmp_work);
get_dp(member, qualitySize, k - 1, dp);
for (int i = 0; i <= qualitySize - k; i++) {
int total = member[i].q;
if (k != 1)
total += dp[i + 1];
cost = total * member[i].w_p_q;
if (cost < ans)
ans = cost;
}
return ans;
}
int main() {
int q1[] = {10, 20, 5}, w1[] = {70, 50, 30}, q2[] = {3, 1, 10, 10, 1},
w2[] = {4, 8, 2, 2, 7};
printf("%f\n", mincostToHireWorkers(q1, ARRAY_SIZE(q1), w1, ARRAY_SIZE(w1),
2)); // expect: 105.0000
printf("%f\n", mincostToHireWorkers(q2, ARRAY_SIZE(q2), w2, ARRAY_SIZE(w2),
3)); // expect: 30.6667
}
|