Как избавиться от TLE?

Question

я решил следующую challenge с помощью грубой силы:

Дано N мешков, каждый мешок содержит Ai шоколад. Есть ребенок и волшебник . За одну единицу времени ребенок выбирает случайный мешок i, ест Ai конфет, затем волшебник заполняет i-й мешок напольным (Ai/2)шоколадом.

Данные Ai для 1 < = i < = N, найти максимальное количество шоколадных конфет можно съесть в K единиц времени.

Например,

К = 3 N = 2 А = 6 5

Возврат: 14

при Т = 1 ребенок ест 6 конфет из мешка 0, и мешок заполняется путем 3 шоколада В t = 2 ребенок ест 5 конфет из мешка 1, а сумка заполняется 2 конфетами В t = 3 ребенок ест 3 шоколада из мешка 0, , и сумка заполняется 1 шоколадом, поэтому общее количество шоколад едят: 6 + 5 + 3 = 14

Примечание: Возврат ваш ответ по модулю 10^9 + 7

Сначала я взял массив в вектор пары, который первым элементом является значение и второй элемент индекса. то я нахожу максимальное значение из вектора, а также изменяю это значение.

К сожалению, это занимает слишком много времени.
Есть ли лучший способ?

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 1

Ваш алгоритм имеет порядок O (N * K), потому что вы проверяете каждый мешок на каждый шаг.

Вместо этого используйте кучу A _i и всегда берем верхний элемент для алгоритма порядка O (K * log N).

Вы хотите push_heap, pop_heap и make_heap от <algorithm>.