-
Notifications
You must be signed in to change notification settings - Fork 0
/
Chocola_Problem.java
70 lines (59 loc) · 1.7 KB
/
Chocola_Problem.java
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
package Greedy_Algorithm_Problems;
import java.util.*;
public class Chocola_Problem {
public static void main(String[] args) {
int[] costVer = {4, 3, 2, 1, 1};
int[] costHor = {4, 2, 1};
System.out.println(chocola(costHor, costVer));
}
public static int chocola(int[] costHor, int[] costVer) {
int ans = 0;
// Sort in descending order
Arrays.sort(costHor);
int start = 0;
int end = costHor.length-1;
while (start <= end){
int temp = costHor[start];
costHor[start] = costHor[end];
costHor[end] = temp;
start++;
end--;
}
Arrays.sort(costVer);
start = 0;
end = costVer.length-1;
while (start <= end){
int temp = costVer[start];
costVer[start] = costVer[end];
costVer[end] = temp;
start++;
end--;
}
// get greedy about maximum cost slice first
int h = 0, v = 0;
int hp = 1, vp = 1;
while (h < costHor.length && v < costVer.length){
if (costHor[h]<=costVer[v]){
ans += costVer[v] * hp;
v++;
vp++;
}else{
ans += costHor[h] * vp;
h++;
hp++;
}
}
// left elements in arrays
while (h < costHor.length){
ans += costHor[h] * vp;
h++;
hp++;
}
while(v < costVer.length){
ans += costVer[v] * hp;
v++;
vp++;
}
return ans;
}
}