{"id":294,"date":"2013-05-31T12:49:49","date_gmt":"2013-05-31T04:49:49","guid":{"rendered":"http:\/\/blog.dayandcarrot.net\/?p=294"},"modified":"2013-05-31T12:49:49","modified_gmt":"2013-05-31T04:49:49","slug":"1051-pop-sequence-25","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=294","title":{"rendered":"1051. Pop Sequence (25)"},"content":{"rendered":"<p>Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, &#8230;, 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.<br \/>\n<b>Input Specification:<\/b><br \/>\nEach input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.<br \/>\n<b>Output Specification:<\/b><br \/>\nFor each pop sequence, print in one line &#8220;YES&#8221; if it is indeed a possible pop sequence of the stack, or &#8220;NO&#8221; if not.<br \/>\n<b>Sample Input:<\/b><\/p>\n<pre>5 7 5\n1 2 3 4 5 6 7\n3 2 1 7 5 6 4\n7 6 5 4 3 2 1\n5 6 4 3 7 2 1\n1 7 6 5 4 3 2<\/pre>\n<p><b>Sample Output:<\/b><\/p>\n<pre>YES\nNO\nNO\nYES\nNO<\/pre>\n<p>=================================<br \/>\n\u6570\u636e\u7ed3\u6784\u662f\u4e2a\u597d\u4e1c\u897f\u3002<br \/>\n\u8f93\u5165\u7684\u5e8f\u52171,2,3\uff0c&#8230;\uff0cN\u5176\u5b9e\u662f\uff08\u5e9f\u8bdd\u672c\u6765\u5c31\u662f\uff09\u4e00\u4e2a\u961f\u5217(\u4e0b\u9762\u8bb0\u4f5cseq)\uff0c\u7136\u540e\u5728\u5f04\u4e00\u4e2a\u5bb9\u6613\u88ab\u586b\u6ee1\u7684\u6808&#8230;<br \/>\n\u4ee5\u4e0b\u6808\u5e95\u3001\u961f\u9996\u7528#\u53f7\u6807\u8bc6<br \/>\n\u7136\u540e\u770b\u6d4b\u8bd5\u7684\u5e8f\u5217\uff0c\u6bd4\u59825 6 4 3 7 2 1\uff0c<br \/>\n1.\u5148\u770b\u6808\u9876\u5143\u7d20\uff0c\u5982\u679c\u6808\u9876\u5143\u7d20\u5c31\u662f\u8f93\u5165\u7684\u5143\u7d20\u7684\u8bdd\uff0c\u90a3\u5c31\u5f39\u6808\uff0c\u7136\u540e\u7ee7\u7eed\u5faa\u73af<br \/>\n2.\u5982\u679c\u4e0d\u662f\uff0c\u90a3\u4e48\u5c31\u8981\u5c06\u961f\u5217\u7684\u5934\u4e00\u76f4\u53d6\u51fa\uff0c\u586b\u5230\u6808\u91cc\u9762\uff0c<br \/>\n\u76f4\u5230\uff1a(A)\u6808\u6ee1\u4e86\uff0c\u90a3\u4e48\u5931\u8d25\u4e86<br \/>\n     (B)\u73b0\u5728\u6808\u9876\u7684\u5143\u7d20\u5c31\u662f\u6211\u4eec\u7684\u8f93\u5165\u5143\u7d20\uff0c\u90a3\u4e48\u7ee7\u7eed\u8bfb\u4e0b\u4e00\u4e2a\u6d4b\u8bd5\u7684\u6570\u5b57<br \/>\n\u6d4b\u8bd5\u5e8f\u52175 6 4 3 7 2 1\u4e2d\uff0c\u4e00\u5f00\u59cb\u7684\u5143\u7d20\u662f5\uff0c\u4e8e\u662f\u4e0d\u65ad\u7684\u4ece1234567\u8fd9\u4e2a\u961f\u5217\u4e2d\u53d6\u5934\u90e8\u51fa\u6765\uff0c\u538b\u6808\uff0c\u7136\u540e<br \/>\n\u6808S : #1 2 3 4 5<br \/>\nseq:  # 6 7<br \/>\n\u6ee1\u8db3\u8c03\u8282\u540e\uff0c\u4e0b\u4e00\u4e2a\u5faa\u73af\u67e5\u770b\u7684\u65f6\u5019\uff0c\u53d1\u73b0\u6808\u9876\u76845\u521a\u597d\u662f\u6211\u4eec\u7684\u8f93\u5165\u5143\u7d20\uff0c\u4e8e\u662f\u5e8f\u5217\u6307\u9488\u79fb\u52306\u4e0a\u9762\uff0c\u5e76\u4e14\u5f39\u51fa5\uff0c<br \/>\n\u7ecf\u8fc7\u5dee\u4e0d\u591a\u7684\u8fc7\u7a0b\uff0c\u53d8\u6210\u8fd9\u6837<br \/>\n\u6808S : #1 2 3 4 6<br \/>\nseq : #7<br \/>\n\u4e4b\u540e\u8fd9\u6837<br \/>\n\u6808S : #1 2 3 4<br \/>\nseq : #7<br \/>\n,<br \/>\n\u6808S : #1 2 3<br \/>\nseq : #7<br \/>\n,<br \/>\n\u6808S : #1 2<br \/>\nseq : #7<br \/>\n,<br \/>\n\u6808S : #1 2 7<br \/>\nseq : #<br \/>\n,<br \/>\n\u6808S : #1 2<br \/>\nseq : #<br \/>\n,<br \/>\n\u3002\u3002\u3002\u76f4\u5230\u5c3d\u5934\uff0c\u7136\u540e\u6210\u529f\u4e86<br \/>\n=======================================================<br \/>\n\u5177\u4f53\u5b9e\u73b0\u53ef\u80fd\u8ddf\u521a\u624d\u7684\u8bf4\u6cd5\u7565\u6709\u4e0d\u4e00\u81f4\uff0c\u4f46\u662f\u539f\u7406\u662f\u4e00\u6837\u7684\u3002<\/p>\n<pre>\n#include <stdio.h>\n#include <queue>\n#include <stack>\nusing namespace std;\nint main()\n{\n    int M, N, K;\n    queue<int> sequences;\n    queue<int> copy_of_seq; \/\/\u4e3a\u4e86\u9632\u6b62\u91cd\u590d\u751f\u6210\u6d6a\u8d39\u65f6\u95f4\n    scanf(\"%d %d %d\", &M, &N, &K);\n    \/\/\u751f\u6210seq\u961f\u5217\n    for(int i=1; i<n+1; i++)\n    {\n        sequences.push(i);\n    }\n    while(K--)\n    {\n        copy_of_seq = sequences;\n        stack<int> s;\n        bool failed = false;\n        int input_val;\n        for(int i=0; i<n; i++)\n        {\n            scanf(\"%d\", &#038;input_val); \/\/\u8bfb\u53d6\u4e00\u4e2a\u6570\u5b57\n            if(failed)\n                continue;\/\/\u628a\u8fd9\u884c\u8bfb\u5b8c\n            if( (!s.empty()) &#038;&#038; (input_val==s.top()))\n            {\n                \/\/\u5f53\u524d\u6808\u9876\u5c31\u662f\u8fd9\u4e2a\u503c\n                s.pop();\n                continue;\n            }\n            while( (!copy_of_seq.empty()) &#038;&#038; (input_val!=copy_of_seq.front()) )\n            {\n                \/\/\u5f53\u5e8f\u5217\u5934\u90e8\u4e0e\u8f93\u5165\u6570\u5b57\u4e0d\u4e00\u6837\u65f6\uff0c\u4e0d\u65ad\u538b\u6808\uff0c\u5982\u679c\u6808\u6ee1\u4e86\u90a3fail\n                s.push( copy_of_seq.front() );\n                copy_of_seq.pop();\n                if ( s.size() >= M) \/\/\u8981\u7559\u4e00\u4e2a\u7ed9\u540e\u9762\u518d\u8bfb\u5165\u7684\u76f8\u7b49\u7684\u5143\u7d20\n                {\n                    failed = true;\n                    break;\n                }\n            }\n            if( failed )\n            {\n                printf(\"NOn\");\n            }\n            else if( copy_of_seq.empty() )\n            {\n                failed = true;\n                printf(\"NOn\");\n            }\n            else\n            {\n                \/\/\u6210\u529f\u4e86..\n                \/\/s.push( copy_of_seq.front() ); (\u53cd\u6b63\u8fd8\u8981pop\uff0c\u4e0d\u641e\u4e86)\n                copy_of_seq.pop();\n            }\n            \/\/\u5982\u679c\u5934\u90e8\u8fd8\u662f\u4e0e\u6570\u5b57\u4e0d\u540c\uff0c\u90a3\u5c31fail\n        }\n        if (!failed)\n            printf(\"YESn\");\n    }\n    return 0;\n}\n<\/pre>\n<p>\u6d4b\u8bd5\u70b9\t\u7ed3\u679c\t\u7528\u65f6(ms)\t\u5185\u5b58(kB)\t\u5f97\u5206\/\u6ee1\u5206<br \/>\n0\t\u7b54\u6848\u6b63\u786e\t0\t740\t15\/15<br \/>\n1\t\u7b54\u6848\u6b63\u786e\t0\t750\t3\/3<br \/>\n2\t\u7b54\u6848\u6b63\u786e\t0\t790\t2\/2<br \/>\n3\t\u7b54\u6848\u6b63\u786e\t0\t790\t2\/2<br \/>\n4\t\u7b54\u6848\u6b63\u786e\t0\t750\t1\/1<br \/>\n5\t\u7b54\u6848\u6b63\u786e\t0\t780\t2\/2<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, &#8230;, 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 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[84],"class_list":["post-294","post","type-post","status-publish","format-standard","hentry","category-study","tag-pat"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/294","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=294"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/294\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=294"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=294"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=294"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}