There are n
bricks arranged in a row at positions numbered from 1
through n
, inclusive. There is an array, newtons[n]
, that contains an integer indicating the number of newtons required to smash a brick. (A newton is a unit of force.)
There are two hammers, one big and one small. The big hammer can smash any brick with one blow. The small hammer reduces the newtons required by 1
for each blow to a brick. For example, a brick requires 3
newtons of force. It will take 1
blow with the big hammer, or 3
blows with the small hammer to smash it. There is a limit to how many times the big hammer can be used.
Determine 3
values:
[[total hits], [big hammer hits], [small hammer hits]]
. If a hammer is not used, its index array should be [-1]
.
Function Description
Complete the function breakTheBricks
in the editor below.
breakTheBricks
has the following parameters:
int bigHits
: the maximum blows with the big hammerint newtons[n]
: an array of distinct integers representing newtons required to smash each brickReturns
long[[1], [p][q]]
: IN THE FORM [[total hits], [sorted indices for big hammer hits], [sorted indices for small hammer hits]]
Example 1:
Input: bigHits = 0, newtons = [2]
Output: [[2], [-1], [1]]
Explanation:The big hammer cannot be used. The small hammer takes2
blows to smash the single brick at index1
. The return array is[[2], [-1], [1]]
.
Example 2:
Input: bigHits = 4, newtons = [3, 2, 5, 4, 6, 7, 9]
Output: [[13], [3, 5, 6, 7], [1, 2, 4]]
Explanation:In this case, it is best to use the big hammer on bricks at sorted indices[3, 5, 6, 7]
using4
hits to smash them all. The small hammer is used on sorted indices[1, 2, 4]
which have newtons of3, 2, and 4
. It takes a total of3 + 2 + 4 = 9
hits with the small hammer. The total blows required =4 + 9 = 13
. The return array is[[13], [3, 5, 6, 7], [1, 2, 4]]
.
Example 3:
Input: bigHits = 9, newtons = [7, 9, 3, 2, 5, 8, 4, 6]
Output: [[8], [1, 2, 3, 4, 5, 6, 7, 8], [-1]]
Explanation:There are enough bigHits available to smash all of the bricks with the large hammer. The returned array is [[8], [1, 2, 3, 4, 5, 6, 7, 8], [-1]].
Example 4:
Input: bigHits = 0, newtons = [10000000, 100000000, 1000000000]
Output: [[1110000000], [-1], [1, 2, 3]]
Explanation:Since bigHits = 0, the big hammer cannot be used. The total hits required is the sum of the newtons array, one hit with a small hammer for each newton. The returned arr is [[1110000000], [-1], [1, 2, 3]].
1 ≤ n ≤ 2x105
0 ≤ bigHits ≤ 2x105
1 ≤ newtons[n] ≤ 109

input:
output: