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
|
// 1046. Last Stone Weight
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
/*
* you are given an array of integers 'stones' where 'stones[i]' is the weight
* of the i'th stone. on each turn, we choose the heaviest two stones and smash
* them together suppose the heaviest two stones have weights x and y with x <=
* y. the result of the smash is if x == y, both stones are destroyed. and if x
* != y, the stone of weight x is destroyed, and the stone of weight y has new
* weight y - x. at the end of the game there is at most one stone left. return
* the weight of the remaining stone or zero.
*/
int lastStoneWeight(int *stones, int stones_size) {
int h[1001] = {}, mx = INT_MIN;
for (int i = 0; i < stones_size; ++i) {
h[stones[i]]++;
mx = fmax(mx, stones[i]);
}
int w = mx;
h[w]--;
while (w) {
if (h[w]) {
if (mx) {
int d = mx - w;
h[d]++;
h[w]--;
w = fmax(w, d);
mx = 0;
} else {
h[w]--;
mx = w;
}
} else
--w;
}
return mx;
}
int main() {
int s1[] = {2, 7, 4, 1, 8, 1}, s2[] = {1};
printf("%d\n", lastStoneWeight(s1, 6)); // expect: 1
printf("%d\n", lastStoneWeight(s2, 1)); // expect: 1
}
|