如何擺脫TLE？

-2

給定N袋，每袋含有艾巧克力。有一個孩子和一個魔術師。在一個單位的時間裏，孩子選擇一個隨機袋子i，吃巧克力，然後魔術師用巧克力（Ai/2）巧克力填充第i個袋子。

給定Ai爲1 < = i < = N，找到最大巧克力數量小孩可以吃K單位時間。

例如，

K = 3，N = 2 A = 6 5

回程：14

在t = 1點的孩子吃從袋0 6克的巧克力，以及所述袋被通過填充 3個巧克力在t = 2小孩從袋1吃5個巧克力，並且袋由2個巧克力填充在t = 3小孩從袋0, 吃3個巧克力，並且該袋由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; 
}

來源

2016-11-05 akid

如果孩子們吃了那麼多的巧克力，他們有發生糖尿病的風險。 – 2016-11-05 15:50:41

@RawN對更好的算法的一個不雅的請求，這就是我添加標籤的原因。 – Deduplicator

@複製器這對你很好。有耐心的榮譽通過該措辭的榮譽。 – 2016-11-05 15:58:23

您的算法的訂單爲O（N * K），因爲您爲每一步檢查每個包。

取而代之，使用一堆A _i，並且始終將頂層元素用於O（K * log N）的算法。

您想要push_heap,pop_heap和make_heap從<algorithm>。

來源

2016-11-05 15:47:27 Deduplicator

如何擺脫TLE？

回答

相關問題