Башня из ведра - ускорение Алгоритм

Question

Мне нужно ускорить мой алгоритм. Речь идет о поиске высоты башни. Башня строится из ведра. Каждое ведро имеет высоту и радиус (1 <= высота, радиус <= 1000). Переменная <code>bucketCount описывает, сколько ковшей размещено на башне (1 <= bucketCount <= 10 <sup>6 ). Мы устанавливаем ведра в последовательности. Толщина ковша 0 (для простоты)

Изображение примера башни

Я решил использовать стек. Мой алгоритм для каждого ведра:

1. Если стек пуст, тогда вставить стек в стек,
2. Если ведро, которое я держу, уже, чем ведро сверху, положите его в стек
3. Иначе, когда ведро, которое я держу, шире: вытолкните и найдите максимальную высоту (для нового основания ковша), после того, как ведро, которое я держу.

Для каждого ковша я добавил дополнительную переменную массу, которая указывает, на какой высоте ковш установлен. Между тем я держу максимальную высоту башни в переменной.

Полагаю, это занимает слишком много времени, но я не могу найти способ его обмануть. Есть ли способ ускорить? Я использовал профилирование и знаю, что top() занимает много времени.

Пример ввода: 2 20 20 30 30
Выход: 50

#include <iostream>
#include <stack>

using namespace std;

class Bucket{
public:
    int height;
    int radius;
    int ground;
};

int main()
{
    stack<Bucket> tower;
    int hightestPoint = 0;
    int bucketCount;
    cin >> bucketCount;
    Bucket temp;
    int maksimum;
    int sum;
    for(int i = 0; i < bucketCount; i++){
        cin >> temp.radius >> temp.height;
        maksimum = -1;
        sum = 0;
        if(tower.empty()){
            temp.ground = 0;
            tower.push(temp);
        } else {
            if(temp.radius < tower.top().radius){ //If bucket is narrower then push it
                temp.ground = tower.top().ground;
                tower.push(temp);
            } else { //If bucket is wider
                while(!tower.empty() && temp.radius >= tower.top().radius){ //Pop and search for new ground (maximum)
                    sum = tower.top().height + tower.top().ground;
                    if(maksimum < sum){
                        maksimum = sum;
                    }
                    tower.pop();
                }
                temp.ground = maksimum; //Set ground for new bucket
                tower.push(temp);
            }
        }
        sum = tower.top().height + tower.top().ground; //Meantime find highest point in stack
        if(hightestPoint < sum){
            hightestPoint = sum;
        }
    }
    cout << hightestPoint << endl;

    return 0;
}

Обновление № 1

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Bucket{
public:
    int height;
    int radius;
    int ground;
};

bool compareBuckets(Bucket a, Bucket b){
    if(a.radius > b.radius){
        return true;
    } else {
        return false;
    }
}

bool compareMax(Bucket a, Bucket b){
    if((a.height + a.ground) > (b.height + b.ground)){
        return true;
    } else {
        return false;
    }
}

int main()
{
    int ile;
   // cin >> ile;
   ile = 1;
    for(int p = 0; p< ile; p++){
        vector<Bucket> tower;
        int hightestPoint = 0;
        int bucketCount;
       // cin >> bucketCount;
        bucketCount = 1000000;
        Bucket temp;
        vector<Bucket>::iterator low;
        vector<Bucket>::iterator element;
        int sum;
        for(int i = 0; i < bucketCount; i++){
            //cin >> temp.radius >> temp.height;
            temp.radius = i % 1000;
            temp.height = i % 1000;
            sum = 0;
            if(tower.empty()){
                temp.ground = 0;
                tower.push_back(temp);
            } else {
                if(temp.radius < tower.back().radius){ //If bucket is narrower then push it
                    temp.ground = tower.back().ground;
                    tower.push_back(temp);
                } else { //If bucket is wider
                    low= lower_bound (tower.begin(), tower.end(), temp,compareBuckets);
                    element = max_element(low, tower.end(), compareMax);
                    Bucket b = tower.at(element-tower.begin());
                    temp.ground = b.ground + b.height;//Set ground for new bucket
                    tower.erase(low, tower.end());
                    tower.push_back(temp);
                }
            }
            sum = tower.back().height + tower.back().ground; //Meantime find highest point in stack
            if(hightestPoint < sum){
                hightestPoint = sum;
            }
        }
        cout << hightestPoint << endl;
    }

    return 0;
}

Answer 1

Редактировать: как указал Мэтт, редактирование не требуется.

Оператор while проходит по стеку и находит корзину только шире, чем новую. По сути, это поиск элемента в списке, который меньше, чем какой-то новый элемент. Что легко сделать с помощью бинарного поиска или сохранения списка в наборе.

Чтобы реализовать это, вы можете использовать vector для поддержки вашего стека и затем lower_bound , чтобы найти соответствующий сегмент.