Оптимизация кода для решения задачи

207
29 марта 2018, 09:23

Здравствуйте, возникла проблема, сайт для проверки решения выдает превышение лимита времени. Как и что тут можно оптимизировать?

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main()
{
   long long i, n;
   cin >> n;
   stack <long long> A;
   stack <long long> B;
   vector <long long> C;
   for (i = 0 ; i < n ; i ++)
   {
      char x;
      long long X, k;
      cin >> x;
      switch ( x )
      {
         case '+':
         {
            cin >> X;
            A.push (X);
            break;
         }
         case '-':
         {
            C.push_back (A.top ());
            A.pop ();
            break;
         }
         case '?':
         {
            cin >> X;
            long long s=0;
            for (k=0 ; k<X ; k++)
            {
               s += A.top ();
               B.push (A.top ());
               A.pop ();
            }
            C.push_back (s);
            for (k=0 ; k < X ; k++)
            {
               A.push (B.top ());
               B.pop ();
            }
            break;
         }
      }
   }
   while (C.size() != 0)
   {
      cout << C[0] << endl;
      C.erase (C.begin ());
   }
}
Answer 1

Вам нужно хранить не только данные, но и готовые суммы - с нуля до текущего элемента. Тогда нужная сумма находится просто как разность двух значений...

Примерно так:

#include <vector>
#include <iostream>
#include <numeric>
#include <limits>
using namespace std;
struct Data
{
    int val;
    long long sum;
};
vector<Data> base{{0,0ll}};
int main()
{
    int n;
    cin >> n;
    base.reserve(n);
    for(int i = 0; i < n; ++i)
    {
        cin.ignore(std::numeric_limits<std::streamsize>::max(),'\n');
        char c; Data d; int k;
        cin.get(c);
        switch(c)
        {
        case '-': {
            cout << base.back().val << endl;
            base.pop_back();
            break;
        }
        case '+': {
            cin >> d.val;
            d.sum = base.back().sum + d.val;
            base.push_back(d);
            break;
        }
        case '?': {
            cin >> k;
            cout << (base.back().sum - (base.end()-k-1)->sum) << endl;
            break;
        }
        }
    }
}
READ ALSO
Вывод логов действий с файлами

Вывод логов действий с файлами

Где найти файл лога Win с информацией о, например, кол-ве удалённых папок или файлов? Ну, не само количество, а, допустим, просто инфу о том, какие...

208
Ошибка памяти или синтаксиса С++

Ошибка памяти или синтаксиса С++

Добрый вечерПишу код программы, которая должна иметь функции ввода и вывода массива типа структуры AEROFLOT

218
Почему не работает цикл while?

Почему не работает цикл while?

Провожу эксперименты с Arduino и решил замучать цикл while (вместо loop)Задал условие, при котором должен срабатывать цикл, но вместо срабатывания...

236
Не работает цикл while в Arduino?

Не работает цикл while в Arduino?

Вот код на дёргание светодиода каждую секунду:

228