generated from threeal/project-starter
-
Notifications
You must be signed in to change notification settings - Fork 1
/
solution.c
58 lines (45 loc) · 1.48 KB
/
solution.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
#include <stdlib.h>
struct project_t {
int profit;
int capital;
};
int compProject(const void* a, const void* b) {
return ((struct project_t*)a)->capital != ((struct project_t*)b)->capital
? ((struct project_t*)a)->capital - ((struct project_t*)b)->capital
: ((struct project_t*)a)->profit - ((struct project_t*)b)->profit;
}
int compInt(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
int findMaximizedCapital(
int k, int w,
int* profits, int profitsSize,
int* capital, int capitalSize) {
(void)capitalSize;
struct project_t* projects = malloc(profitsSize * sizeof(struct project_t));
for (int i = profitsSize - 1; i >= 0; --i) {
projects[i].profit = profits[i];
projects[i].capital = capital[i];
}
qsort(projects, profitsSize, sizeof(struct project_t), compProject);
struct project_t* projectsIt = projects;
struct project_t* projectsEnd = projects + profitsSize;
int* maxProfits = malloc(profitsSize * sizeof(int));
int* maxProfitsIt = maxProfits;
while (--k >= 0) {
if (projectsIt != projectsEnd && projectsIt->capital <= w) {
do {
*maxProfitsIt = projectsIt->profit;
++maxProfitsIt;
++projectsIt;
} while (projectsIt != projectsEnd && projectsIt->capital <= w);
qsort(maxProfits, maxProfitsIt - maxProfits, sizeof(int), compInt);
}
if (maxProfitsIt == maxProfits) return w;
--maxProfitsIt;
w += *maxProfitsIt;
}
free(maxProfits);
free(projects);
return w;
}