c++ - 提高c++中优先级队列的时间复杂度

Question

在下面的代码中，我为更大的 vector 长度超时，尽管它适用于更小的长度 vector 。

     long priceCalculate(vector < int > a, long k) {
        long price = 0;
        priority_queue<int>pq(a.begin(),a.end());
        while(--k>=0){
            int x = pq.top();
            price = price + x;
            pq.pop();
            pq.push(x-1);
        }
        return price;
    }

我有一个数字数组。我必须将最大数量加到 price 上，然后将该数字减 1。再次找到最大数量，依此类推。我必须重复这个过程 k 次。 有没有比优先级队列更好的时间复杂度更低的数据结构？

下面是使用 vector 排序的代码:

    struct mclass {
        public: bool operator()(int x, int y) {
            return (x > y);
        }
    }
    compare;
    long priceCalculate(vector < int > a, long k) {

        long price = 0;
        sort(a.begin(), a.end(), compare);
        while (--k >= 0) {
            if (a[0] > 0) {

                price = price + a[0];
                a[0] = a[0] - 1;

                sort(a.begin(), a.end(), compare);
            }
        }
        return price;
    }

但这也会在大输入长度时超时。

Answer 1

排序代码有两个性能问题:

1. 您正在使用 vector<>在每次迭代中。即使您的排序算法是插入排序(在这种情况下最好)，它仍然需要在声明 vector<> 之前触及 vector 中的每个位置。排序。

2. 更糟糕的是，您将要处理的值排序到 vector 的前面，需要后续的 sort()调用以移动几乎所有元素。

因此，您可以通过以下方式实现巨大的加速

1. 反转排序顺序，以便您只与 vector<> 的末尾进行交互.

2. 只排序一次，然后更新 vector<> 从末尾扫描到正确的位置，并在那里插入新值。

您还可以仔细查看您的算法在做什么:它只在 vector<> 的尾部运行。它具有常量值，从中删除条目，然后重新插入它们，在它前面减一。我认为您应该能够利用这些知识显着简化您的算法，从而实现更显着的加速。最后，您可以从 vector<> 中删除该尾部。完全:它完全由它的长度和它的值来描述，并且它的所有元素都可以在一个操作中被操纵。一旦您完成优化，您的算法应该不会花费任何时间...