首页 > 代码库 > Pop Sequence

Pop Sequence

2024-09-10 08:19:26   206人阅读

题目描述

Given a stack which can keep MM numbers at most. Push NN numbers in the order of 1, 2, 3, ..., NN 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 MM is 5 and NN is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

输入


每个输入文件包含一个测试用例。对于每种情况，第一行包含3个数字（不超过1000）：MM（堆栈的最大容量），NN（推送序列的长度）和KK（要检查的弹出序列的数量）。然后KK线跟随，每个包含NN数字的弹出序列。一行中的所有数字由空格分隔。

输出


对于每个弹出序列，如果确实是堆栈的可能弹出序列则在一行中打印“YES”，否则打印为“NO”。

样例输入

5 7 5 1 2 3 4 5 6 7 3 2 1 7 5 6 4 7 6 5 4 3 2 1 5 6 4 3 7 2 1 1 7 6 5 4 3 2

样例输出

YES NO NO YES NO
 
 
 
 1 #include<iostream>
 2 using namespace std;
 3 int tongji(bool f[],bool f1[],int x)
 4 {
 5     int count=0;
 6     for(int i=1;i<=x;i++)
 7     if(f[i]==0&&f1[i]==0)count++;
 8     return count;
 9 }
10 int main()
11 {
12     /*若当前需要输出X，判断：
13     1，若栈为空，判断X是否大于K，是则NO，否则继续。
14     2，X的下一个数若小于X，判断栈顶元素是否与其相等，是则继续，否则NO。
15     3，X的下一个数若大于X，判断栈剩下的空间是否能容纳没输出过的&&比其小的元素，是则继续，否则NO。
16     */
17     int s[10000],top,a[10000],m,n,k,i,j;
18     cin>>m>>n>>k;
19     while(m--)
20     {
21         top=0;
22         bool f[10000]={0};
23         bool f1[10000]={0};
24         for(i=1;i<=n;i++)
25         cin>>a[i];
26         for(i=1;i<n;i++)
27         {
28             if(top==0)
29             {
30                 if(tongji(f,f1,a[i])>k)break;
31                 else
32                 {
33                     j=1;
34                     while(j<=a[i])
35                         {if(f[j]==0&&f1[j]==0)s[++top]=j;f1[j]=1;j++;}
36                     f[a[i]]=1;
37                     top--;
38                     f1[a[i]]=0;
39                 }
40             }
41             if(a[i+1]<a[i])
42             {
43                 if(a[i+1]!=s[top])break;
44                 else {f[i+1]=1;top--;}
45             }
46             if(a[i+1]>a[i])
47             {
48                 if(tongji(f,f1,a[i+1])>k-top)break;
49                 else
50                 {
51                     j=1;
52                     while(j<=a[i+1])
53                         {if(f[j]==0&&f1[j]==0)s[++top]=j;f1[j]=1;j++;}
54                     f[a[i]]=1;
55                     top--;
56                     f1[a[i]]=0;
57                 }
58             }
59         }
60         if(i==n)cout<<"YES"<<endl;
61         else cout<<"NO"<<endl;
62     }
63     return 0;
64 }

 

 

 

这道题目，首先弄懂英文题意就花了很多时间，考试时候因为看不懂所以直接没做……

懂了题意之后，AC掉花了差不多2个小时……

所以即使考试时候看明白题意我也不会当场做出来啊- -

真心觉的自己菜得不行

不知不觉已经大二下学期了，然而自己的水平其实和大一时候没什么区别，

就拿畅通工程的问题来说，考了不下3次，每一次不会都不知道把它弄懂

自己了解的算法太少了，虽然这学期才开始上算法课，但是比赛什么的已经早早用到了

完全可以多做一些代表性的题目，拿出来好好研究一下，哪怕一晚上研究一道题，以后也可以举一反三利用了。

还有十多天比赛，在这之前每天弄明白一到两个典型的算法问题，到时候也可以有很大的进步了，希望不要辜负自己吧

Pop Sequence


联系
我们