c++ - How to get rid of TLE? -

i solved following challenge brute-force:

given n bags, each bag contains ai chocolates. there kid , magician. in 1 unit of time, kid chooses random bag i, eats ai chocolates, magician fills ith bag floor(ai/2) chocolates.

given ai 1 <= <= n, find maximum number of chocolates kid can eat in k units of time.

for example,

k = 3 n = 2 = 6 5

return: 14

at t = 1 kid eats 6 chocolates bag 0, , bag gets filled 3 chocolates @ t = 2 kid eats 5 chocolates bag 1, , bag gets filled 2 chocolates @ t = 3 kid eats 3 chocolates bag 0, , bag gets filled 1 chocolate so, total number of chocolates eaten: 6 + 5 + 3 = 14

note: return answer modulo 10^9+7

first took array in vector pair first element value , 2nd element index. find max value vector , change value.

unfortunately, takes long.
there 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; } 

your algorithm has order o(n*k), because check every bag every step.

instead, use heap of a_i, , take top-element algorithm of order o(k*log n).

you want push_heap, pop_heap , make_heap <algorithm>.