akid - 1 year ago 169

C++ Question

I solved the following challenge by brute-force:

Given N bags, each bag contains Ai chocolates. There is a kid and a

magician. In one unit of time, kid chooses a random bag i, eats Ai

chocolates, then the magician fills the ith bag with floor(Ai/2)

chocolates.

Given Ai for 1 <= i <= N, find the maximum number of chocolates kid

can eat in K units of time.

For example,

K = 3 N = 2 A = 6 5

Return: 14

At t = 1 kid eats 6 chocolates from bag 0, and the bag gets filled by

3 chocolates At t = 2 kid eats 5 chocolates from bag 1, and the bag

gets filled by 2 chocolates At t = 3 kid eats 3 chocolates from bag 0,

and the bag gets filled by 1 chocolate so, total number of chocolates

eaten: 6 + 5 + 3 = 14

Note: Return your answer modulo 10^9+7

First I took the array in the vector pair which first element is the value and 2nd element is index. then I find the max value from the vector and also change that value.

Unfortunately, that takes too long.

Is there a better way?

`int Solution::nchoc(int A, vector<int> &B) {`

vector<pair<int, int> >vc;

for(int i=0; i<B.size(); i++)

{

vc.push_back(make_pair(B[i],i));

}

int sum=0;

while(A>0)

{

pair<int,int> x=*max_element(vc.begin(),vc.end());

int x1=x.first;

vc[x.second].first= (int) vc[x.second].first/2;

sum=((sum%1000000007)+(x1%1000000007))%1000000007;

A--;

}

return sum;

}

Answer Source

Your algorithm has order O(N*K), because you check every bag for every step.

Instead, use a heap of A_{i}, and always take the top-element for an algorithm of order O(K*log N).

You want `push_heap`

, `pop_heap`

and `make_heap`

from `<algorithm>`

.