如何摆脱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？

回答

相关问题