Picking apples off a tree

Posted by John Retallack on Stack Overflow See other posts from Stack Overflow or by John Retallack
Published on 2010-04-08T22:30:25Z Indexed on 2010/04/09 16:13 UTC
Read the original article Hit count: 195

Filed under:
|
|
|

I have the following problem: I am given a tree with N apples, for each apple I am given it's weight and height. I can pick apples up to a given height H, each time I pick an apple the height of every apple is increased with U. I have to find out the maximum weight of apples I can pick.

1 = N = 100000
0 < {H, U, apples' weight and height, maximum weight} < 231

Example:

N=4  H=100  U=10  

height weight  
  82     30
  91     10
  93      5
  94     15

The answer is 45: first pick the apple with the weight of 15 then the one with the weight of 30.

Could someone help me approach this problem?

© Stack Overflow or respective owner

Related posts about c

    Related posts about c++