Подсчет максимального количества элементов на основе операций со стеком С++

В массиве размером н действительный индекс от 0 до n-1, а не от 1 до н

Предупреждение: когда вы выделяете массив с помощью новый, вы должны освободить его с помощью delete []

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

Например, из вашего кода:

#include <iostream>

using namespace std;

int main()
{
  int n, x, max;

  if ((! (cin >> n)) || (n < 1))
    cerr << "invalid size" << endl;
  else if ((! (cin >> x)) || (x < 0) || (x >= n))
    cerr << "invalid min index" << endl;
  else {
    int* arr = new int[n];
    //Storing the values from the last, since the first element represents 
    //top of the stack, so the first element would be latest element which 
    //will be pushed into the stack
    for (int i = n-1; i >= 0; i--)
    {
      if (!(cin >> arr[i])) {
        cerr << "invalid value" << endl;
        return 0;
      }
    }
    max = arr[n-1];
    //Finding the max by iterating from the last position to the no of 
    //stack operations performed.
    for (int i = n-2; i >= x; i--)
    {
      if (arr[i] > max)
        {
          max = arr[i];
        }
    }
    cout << max << endl;
    delete arr; // must be delete [] arr;
  }
  return 0;
}

Из того факта, что я проверяю, что было введено целое число, я также проверяю, что индекс size/min строго положителен, а также проверяю действительность индекса min.

Также бесполезно зацикливаться, чтобы найти максимальное сравнение arr[n-1] с самим собой, поэтому первым рассматриваемым индексом будет n-2

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

Вы используете массив, но вы также можете использовать vector<int>, std::vector очень практичны

Составление и исполнение:

pi@raspberrypi:/tmp $ g++ -pedantic -Wall -Wextra v.cc
pi@raspberrypi:/tmp $ ./a.out
aze
invalid size
pi@raspberrypi:/tmp $ ./a.out
-1
invalid size
pi@raspberrypi:/tmp $ ./a.out
3 qsd
invalid min index
pi@raspberrypi:/tmp $ ./a.out
3 4
invalid min index
pi@raspberrypi:/tmp $ ./a.out
6 4
1 2 4 3 3 5
2
pi@raspberrypi:/tmp $ 

Обратите внимание, что результат равен 2, а не 4 из-за сдвига в индексе, если вы хотите, чтобы индекс начинался с 1 для пользователя, выполните

#include<iostream>

using namespace std;

int main()
{
  int n, x, max;

  if ((! (cin >> n)) || (n < 1))
    cerr << "invalid size" << endl;
  else if ((! (cin >> x)) || (x < 1) || (x > n))
    cerr << "invalid min index" << endl;
  else {
    x -= 1;

    int * arr = new int[n];
    //Storing the values from the last, since the first element represents 
    //top of the stack, so the first element would be latest element which 
    //will be pushed into the stack
    for (int i = n-1; i >= 0; i--)
    {
      if (!(cin >> arr[i])) {
        cerr << "invalid value" << endl;
        return 0;
      }
    }
    max = arr[n-1];
    //Finding the max by iterating from the last position to the no of 
    //stack operations performed.
    for (int i = n-2; i >= x; i--)
    {
      if (arr[i] > max)
        {
          max = arr[i];
        }
    }
    cout << max << endl;
    delete arr; // must be delete [] arr;
  }
  return 0;
}

Компиляция и исполнение:

pi@raspberrypi:/tmp $ g++ -pedantic -Wall -Wextra v.cc
pi@raspberrypi:/tmp $ ./a.out
6 4
1 2 4 3 3 5
4
pi@raspberrypi:/tmp $ 

Выполнение под валгринд с указанием неправильного free arr:

pi@raspberrypi:/tmp $ valgrind ./a.out
==3761== Memcheck, a memory error detector
==3761== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3761== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==3761== Command: ./a.out
==3761== 
6 4
1 2 4 3 3 5
4
==3761== Mismatched free() / delete / delete []
==3761==    at 0x48491EC: operator delete(void*) (vg_replace_malloc.c:576)
==3761==    by 0x10BE7: main (in /tmp/a.out)
==3761==  Address 0x4bcb388 is 0 bytes inside a block of size 24 alloc'd
==3761==    at 0x48485F0: operator new[](unsigned int) (vg_replace_malloc.c:417)
==3761==    by 0x10A9F: main (in /tmp/a.out)
==3761== 
==3761== 
==3761== HEAP SUMMARY:
==3761==     in use at exit: 0 bytes in 0 blocks
==3761==   total heap usage: 4 allocs, 4 frees, 22,296 bytes allocated
==3761== 
==3761== All heap blocks were freed -- no leaks are possible
==3761== 
==3761== For counts of detected and suppressed errors, rerun with: -v
==3761== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 6 from 3)
pi@raspberrypi:/tmp $ 

В вашем коде есть несколько ошибок: три ошибки индексации и одна ошибка освобождения памяти. Прежде всего, в C++ индексация массива всегда начинается с 0. Таким образом, первый допустимый индекс массива из n элементов равен 0, а последний допустимый индекс равен n-1.

1) По этим причинам первый цикл должен быть таким:

for (int i = n-1; i >= 0; i--) { ... }

2) Нижний элемент, который вы называете «max», должен быть инициализирован следующим образом:

max = arr[n-1];

3) То же наблюдение о втором цикле:

for (int i = n-2; i >= x; i--) { ... }

4) Освобождение массива должно выполняться оператором delete[] вместо delete. В противном случае у вас будет утечка памяти и неопределенное поведение. Здесь вы можете найти дополнительную информацию об этих операторах:

delete[] arr;

Сначала нужно уложить в голове требование:

You are given a stack of N integers. In one operation, you can either pop an element from the stack or push any popped element into the stack. You need to maximize the top element of the stack after performing exactly K operations. If the stack becomes empty after performing K operations and there is no other way for the stack to be non-empty, print -1.

• Итак, если N равно 0, вы печатаете -1, иначе...
• Если K равно 0, вы печатаете top(), иначе...
• Если K равно 1, вам нужно pop(), потому что вам нечего толкать, поэтому, если N равно 1, ваш стек пуст, и вы должны напечатать -1, иначе напечатать top(): каким бы ни был ваш 2-й верхний элемент. ; иначе...
• если x <= N, вы можете вытолкнуть x - 1 элементов, а затем поместить самый большой из них обратно на вершину стека
  • если x == N, обратите внимание, что это означает, что вы все равно не извлечете окончательное значение из стека, поэтому, если это самый большой элемент, вам не повезло: вам придется поместить 2-й по величине обратно вверх стека иначе...
• если x > N, вы можете вытолкнуть все элементы, тратя впустую любые операции, пока у вас не останется только 1 операция (поочередно возвращая любое из не самых больших значений назад, если у вас есть еще одна операция, чтобы вытолкнуть его), затем используя последнюю операцию, чтобы поместить наибольшее значение обратно в стек; это эквивалент для поиска наибольшего значения в стеке

Таким образом, код, который всегда находит наименьший элемент в верхних «x» элементах стека, не моделирует операции стека, которые вы должны иметь в наличии.

То, что вы понимаете, какое значение должна возвращать ваша программа, не означает, что вы не должны точно моделировать операции. Мне кажется, что вы должны использовать операции стека, push, pop и top и отслеживать значения, которые вы извлекли, чтобы при необходимости вы могли вернуть их обратно, и вам может понадобиться найти самое большое из них. ве выскочил, чтобы специально положить его обратно.

Чтобы сделать все это, проще всего использовать структуру данных std::stack и, скажем, std::multiset хранить извлеченные элементы в отсортированном порядке (чтобы вы могли легко найти самый большой из них).

Код выглядит так. Его можно сделать эффективнее/короче, но я оставлю это вам.

#include <iostream>
#include <set>
#include <stack>

#define ASSERT(WHAT, MSG) \
    do { \
        if (!(WHAT)) { \
            std::cerr << "ASSERTION FAILURE AT LINE " \
                << __LINE__ << ": " #WHAT "\n" << MSG << '\n'; \
        } \
    } while (false)

#define DBG(MSG) std::cout << "DBG :" << __LINE__ << " " << MSG << '\n'

// helper functions to be able to stream out containers we're using...
std::ostream& operator<<(std::ostream& os, const std::multiset<int>& s)
{
    os << "{ ";
    for (const auto& x : s) std::cout << x << ' ';
    return os << '}';
}

// note this makes a deep copy of the stack (because "s" is passed by value
// not by reference), so we can pop all the elements destructively
std::ostream& operator<<(std::ostream& os, std::stack<int> s)
{
    os << "{ ";
    while (!s.empty())
    {
        std::cout << s.top() << ' ';
        s.pop();
    }
    return os << '}';
}

int main()
{
    std::stack<int> s;
    std::multiset<int> popped;

    int n, k;

    ASSERT(std::cin >> n >> k, "input must have parseable int values for n and k");

    DBG("n " << n << ", k " << k);
    ASSERT(n >= 0, "n must not be negative");
    ASSERT(k >= 0, "k must not be negative");

    for (int i = 0; i < n; ++i)
    {
        int x;
        ASSERT(std::cin >> x, "input must have parseable int for value #" << i + 1);
        s.push(x);
    }

    DBG("initial stack " << s);

    if (n == 0)
        std::cout << -1 << '\n';
    else if (k == 0)
        std::cout << s.top() << '\n';
    else if (k == 1)
    {
        if (n == 1)
            std::cout << -1 << '\n';
        else
        {
            s.pop(); // have to use up our k1 operation as a pop
            std::cout << s.top() << '\n';
        }
    }
    else if (k <= n) // can't pop all the values
    {
        for (int i = 1; i < k; ++i)
        {
            DBG("popping " << s.top());
            popped.insert(s.top()); // add to popped...
            s.pop(); // ...and remove from stack
        }
        DBG("popped k-1 elements (sorted) " << popped);
        DBG("stack " << s);
        // use the last operation to put the largest popped value back
        // (if the stack's has size 2 or more, could pop another one instead -
        //  no way to know which is better, but if the values are random then
        //  the max of all the popped elements is likely to be more than any
        //  given element)
        s.push(*popped.rbegin());  // largest value seen...
        std::cout << s.top() << '\n';
    }
    else // k > n so can pop all the values...
    {
        DBG("k > n");
        while (!s.empty())
        {
            popped.insert(s.top());
            s.pop();
        }
        // waste however many spare operations we have...
        for (int i = 0; i < k - n - 1; ++i)
            if (i % 2 == 0) // on first, third, fifth iteration...
            {
                DBG("push " << *popped.begin());
                s.push(*popped.begin());  // push lowest value seen back to stack...
                popped.erase(popped.begin());  // ...remove it from popped multiset
            }
            else
            {
                DBG("pop " << s.top());
                popped.insert(s.top());
                s.pop();
            }
        DBG("popped elements (sorted) " << popped);
        DBG("stack " << s);
        s.push(*popped.rbegin());  // push largest value...
        std::cout << s.top() << '\n';
    }
}