-
Notifications
You must be signed in to change notification settings - Fork 0
/
12904_load_balancing.c
73 lines (61 loc) · 1.88 KB
/
12904_load_balancing.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
#include <stdio.h>
#include <math.h>
#define MAX_CREDITS 160
double n_students[MAX_CREDITS];
struct {
int a, b, c;
double cost;
} record;
static void
calculate_record(int a, double N) {
int b, c;
double cost, Ngroup;
Ngroup = N/4;
for(b=a+1; b <= MAX_CREDITS-2; b++) {
for(c=b+1; c <= MAX_CREDITS-1; c++) {
cost = fabs(n_students[a] - Ngroup);
cost += fabs(n_students[b] - n_students[a] - Ngroup);
cost += fabs(n_students[c] - n_students[b] - Ngroup);
cost += fabs(N - n_students[c] - Ngroup);
if(cost < record.cost) {
record.a = a;
record.b = b;
record.c = c;
record.cost = cost;
}
}
}
}
int main() {
int T, credits, ncase, i, a, a_immediately_greater;
double N, a_students;
scanf("%d", &T);
for(ncase=1; ncase<=T; ncase++) {
for(i=0; i<MAX_CREDITS; i++)
n_students[i] = 0.0;
scanf("%lf", &N);
for(i=N; i--; ) {
scanf("%d", &credits);
n_students[credits] += 1.0;
}
/* calculate cumulative sum */
for(i=1; i<MAX_CREDITS; i++)
n_students[i] += n_students[i-1];
/* set a to the first index with cutoff immediately greater to N/4 */
for(a=0; a<MAX_CREDITS && n_students[a] < N/4; a++);
a_immediately_greater = a;
/* set a to the first index with cutoff immediately greater to N/4 */
if(a != 0) {
a--;
a_students = n_students[a];
for(; a>0 && n_students[a] == a_students; a--);
a++;
}
/* max cost is < 10000 */
record.cost = 99999999.;
calculate_record(a, N);
calculate_record(a_immediately_greater, N);
printf("Case %d: %d %d %d\n", ncase, record.a, record.b, record.c);
}
return 0;
}