0

задача

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

#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 ());
   }
}
5
  • C.erase (C.begin ()); Почему бы просто не вывести весь вектор, а потом его полностью не удалить. Удалять первый элемент в векторе очень долго, потому что(если я правильно помню) он создает новый массив и копирует его. Удалять дешевле с конца или весь for(long long i = 0; i < C.size;++i)cout<<C[i]<<endl; C.clear(); 27 мар 2018 в 18:53
  • Не глядя - раз не проходит по времени, оптимизировать нужно не код, а менять алгоритм...
    – Harry
    27 мар 2018 в 18:54
  • Заменить вывод просто по элементам не изменило ничего. А вот про алгоритм идея хорошая, что-нибудь попробую придумать, спасибо!
    – zzronn
    27 мар 2018 в 18:56
  • Есть где-то URL, чтоб зайти и поиграться?
    – Harry
    27 мар 2018 в 19:00
  • Да, конечно. Вот сам сайт, там слева кнопка "Задачи", там очень много задач. А вот именно эта задача
    – zzronn
    27 мар 2018 в 19:04

1 ответ 1

0

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

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

#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;
        }
        }
    }
}
1
  • Ооо, точнооо, спасибо большое, сейчас только постараюсь разобраться в коде. Спасибо огромное!!
    – zzronn
    27 мар 2018 в 20:38

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.