An interesting problem

Правка en1, от wannared, 2017-11-15 23:35:16

Given an array of n numbers A1, A2, ...An,  how many maximum groups I can form from this array, such that the sum of the elements in each group is  ≥ X?

Constraints: N ≤ 106, X ≤ 106,  0 ≤ Ai ≤ X,  Sum of all Ai's  ≤ 106.

For example if Array is

[5, 5, 9, 5, 12, 5] and X is 20. Answer is 2 as we can form 2 groups [5,5,5,5] and [9, 12] such that both groups have sum greater than or equal to 20

I have no idea how to get the optimal solution, Any help is welcome.

Thanks!!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский wannared 2017-11-15 23:35:16 560 Initial revision (published)