首页 > itarticle > pat Thoughts Codes

pat Thoughts Codes

admin 11月 13, 2020 0

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Thoughts

just Stack simulation

Long time no code and my coding ability drops significantly. This problem may be rather simple for some one, but it just serve the purpose of revieweing the basic knowledges for me.

Sometimes a tiny bug can drive you crazy.

No one can come to the final solution at the first glance, but as long as you spend your time on it, it will no doubt seem more ane more clear to you.

Codes

#include <iostream>
using namespace std;
int main(int argc, char const *argv[]) {
  //freopen("D:\cpphomework\test.txt", "r", stdin);
  int m, n, k;cin >> m >> n >> k;
  int **Sequence = new int * [k];
  for (size_t i = 0; i < k; i++) Sequence[i] = new int [n];
  int *used = new int [n+1], *result = new int [n];
  int remaining = m;
  for (size_t i = 0; i < k; i++) {
    result[i] = 1;
    for (size_t j = 0; j < n; j++) {
      cin >> Sequence[i][j];
    }
  }
  //prepare
  for (size_t i = 0; i < k; i++) {
    remaining = m;
    for (size_t j = 1; j <= n; j++) used[j]=0;
    int q = 1, c = 0;
    //start
    while ( q<=n && remaining>0 && result[i] ) {
      if ( q==Sequence[i][c] ) {
        used[q] = 1;
        while ( c+1<n && Sequence[i][c+1]<Sequence[i][c] ) {
          int examine = Sequence[i][c]-1;
          while ( used[examine]==1 ) examine--;
          if ( Sequence[i][c+1]==examine ) {
            used[examine] = 1;
            remaining++;c++;
          }else {
            result[i] = 0;break;
          }
        }
        q++;c++;
      }
      else {
        q++;remaining--;
      }
    }
    if ( q<=n ) {
      result[i] = 0;
    }

    for (size_t j = 1; result[i] && j <= n; j++) {
      if ( used[j]!=1 ) {
        result[j] = 0;
        break;
      }
    }
  }

  //output
  for (size_t i = 0; i < k; i++) {
    switch ( result[i] ) {
      case 1: cout << "YES";break;
      case 0: cout << "NO";break;
    }
    if ( i!=k-1 ) cout << endl;
  }

  //delete
  for (size_t i = 0; i < k; i++) delete [] Sequence[i];
  delete [] Sequence;
  delete [] used;
  delete [] result;
  return 0;
}