774关于priority_pueue的优化

[xymabinogi]

LC-774 priority_queue
顺着您的思路做了一些改进（不会TLE了）：先找到整个数据minmax的upper bound，然后在第一次遇到某个pair时，不要减去1，直接减到低于这个upper bound为止。

Example (借用您的代码)

class Solution {
public:
    double minmaxGasDist(vector<int>& stations, int K) 
    {
        priority_queue<pair<double,int>>pq;
        for (int i=1; i<stations.size(); i++)
            pq.push({stations[i]-stations[i-1],1});
        
        double ub = (stations.back() - stations[0]) / (double) (K + 1);
            
        while (K > 0)
        {
            auto [space, insertNum] = pq.top();
            pq.pop();
            int add = 1;
            if (insertNum == 1)
                add = max(1, int(ceil(space/ub) - 1));
            K -= add;
            pq.push({space*insertNum/(insertNum+add),insertNum+add});            
        }
        
        return pq.top().first;
    }
};

[wisdompeak]

非常感谢！这个思路非常棒，已经在Github更新了，关于这题的视频也重做了一期。

[xymabinogi]

感谢群主！