Оптимизировать код C++ [требует правки]

258

07 сентября 2017, 18:41

Надо оптимизировать код программы как можно сильнее

Задача http://acmp.ru/asp/do/index.asp?main=task&id_course=1&id_section=5&id_topic=114&id_problem=705

Сам код

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
long long a;
long long j = -1, ans;
vector <long long> n;
long long maxi = -100;
int main()
{
    cin >> a;
    long long tmp_g = 1;
    for (int i = 0; i < a; i++){
        cin >> tmp_g;
        n.push_back(tmp_g);
    }
    while (1){
        long long hom = j + 1;
        for(int z = j+1; z < a; z++){
            if(n[z] > n[hom])
                hom = z;
        }
        ans += (hom - j) * n[hom];
        j = hom;
        if (j == a - 1 ) 
        {
            break; 
        }
    }
    cout << ans;
    return 0;
}

Answer 1

Наилучшая оптимизация - всегда начинается с подбора оптимального алгоритма:

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> c(n);
    for (int i = 0; i < n; i++) cin >> c[i];
    int cost = c[n-1], sum = cost;
    for(int j = n-2; j >= 0; --j)
        sum += (cost = max(cost,c[j]));
    cout << sum;
}

Answer 2

Ну я не знаю, насколько этот код вам покажется оптимальней, но я предлагаю вам свой вариант:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n,s=0,prev;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    auto x = a.begin();
    while (x!=a.end())
    {
        prev = x - a.begin();
        x = max_element(x, a.end());
        s += (*x)*(x-a.begin() - prev+1);
        x++;
    }
    cout << s;
}