akid akid - 1 month ago 13
C++ Question

How to get rid of TLE?

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

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

Instead, use a heap of Ai, 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>.