{"id":315,"date":"2021-09-17T11:15:38","date_gmt":"2021-09-17T03:15:38","guid":{"rendered":"https:\/\/aisumura.net\/blog\/?p=315"},"modified":"2021-09-20T23:21:39","modified_gmt":"2021-09-20T15:21:39","slug":"uva11536-smallest-sub-array","status":"publish","type":"post","link":"https:\/\/aisumura.net\/blog\/2021\/09\/17\/uva11536-smallest-sub-array\/","title":{"rendered":"[UVA]11536 Smallest Sub-Array"},"content":{"rendered":"\n<p style=\"font-size:22px\">\u672c\u4eba\u65bc\u8a72blog\u7684\u5168\u90e8\u6587\u7ae0\u8f49\u79fb\u81f3<a href=\"https:\/\/blog.kkwtech.com\/uva\/11536-smallest-sub-array\">[UVA] 11536 Smallest Sub-Array &#8211; KKWBlog (kkwtech.com)<\/a>\u8a72\u7db2\u57df\u4e0b\uff0c\u5176\u5f8c\u6b64\u8655\u4e0d\u9032\u884c\u66f4\u65b0\uff0c\u4e00\u5f8b\u65bc\u65b0\u7ad9\u9ede\u66f4\u65b0\u3002<\/p>\n\n\n\n<p style=\"font-size:22px\"><span class=\"has-inline-color has-retrogeek-foreground-color\">\u984c\u76ee:<\/span><strong><span class=\"has-inline-color has-retrogeek-foreground-color\"> <\/span><\/strong><a href=\"https:\/\/cpe.cse.nsysu.edu.tw\/cpe\/file\/attendance\/problemPdf\/11536.pdf\">11536.pdf (nsysu.edu.tw)<\/a><\/p>\n\n\n\n<p style=\"font-size:24px\">\u984c\u76ee\u8aaa\u660e:<\/p>\n\n\n\n<p>\u7d66\u5b9aN,M,K\u4e26\u4f9d\u7167\u984c\u76ee\u69cb\u5efa\u4e00\u500b\u6578\u5217\uff0c\u627e\u51fa\u6700\u77ed\u4e14\u5305\u542b1~K\u6578\u5b57\u7684sub array\uff0c\u4e26\u8f38\u51fa\u8a72\u9577\u5ea6\u3002<\/p>\n\n\n\n<p style=\"font-size:24px\">\u89e3\u984c\u601d\u8def:<\/p>\n\n\n\n<p>\u904b\u7528queue\u5c07\u7b26\u5408\u689d\u4ef6\u7684sub array\u7684\u6578\u5b57\u653e\u5165queue\uff0c\u82e5queue.front\u7684\u6578\u5b57\u91cd\u8907\u51fa\u73fe\u65bcqueue\u88e1\u5247\u5c07\u5176pop\u51fa\u4f86\uff0c\u53ef\u4ee5\u65bc\u8d70\u8a2a\u6578\u5217\u6642\u7dad\u6301\u76f8\u5c0d\u77ed\u7684sub array\uff0c\u4e26\u4e14\u57281~\uff2b\u90fd\u5728queue\u88e1\u6642\u5f97\u5230\u9577\u5ea6\uff0c\u6700\u5f8c\u5c07\u9577\u5ea6\u53d6\u6700\u5c0f\u5373\u70ba\u8a72\u984c\u89e3\u7b54<\/p>\n\n\n\n<p style=\"font-size:18px\">\u6b65\u9a5f\uff1a<\/p>\n\n\n\n<p>1.\u5275\u5efa1\u9663\u5217\u5b58\u653e&lt;=k\u7684\u6578\u5b57\u6700\u5f8c\u51fa\u73fe\u7684index last_pos<br>2.\u5275\u5efaqueue<br>3.\u5ba3\u544a\u9577\u5ea6minlen\u53ca\u8a08\u7b97sub array\u88e1\u4e0d\u91cd\u8907\u7684\u6578\u5b57\u500b\u6578count<br>4.\u4f9d\u984c\u76ee\u5efa\u69cb\u4e00\u500b\u6578\u5217x<br>5.\u91dd\u5c0d\u6bcf\u500bcur = x[i] \uff0c\u5c07\u5176i\u653e\u5165queue\u4e2d<br>6.\u82e5\u662fcur\u7b26\u5408sub array\u7684\u689d\u4ef6\u7bc4\u570d\u5247\u5c07last_pos[cur] = i\uff0c\u53c8\u82e5last_pos[cur]\u5728\u6b64\u4e4b\u524d\u5c1a\u672a\u653e\u5165queue\u4e2d\u5373\u70ba\u521d\u59cb\u503c\u7684\u8a71\uff0ccount++<br>7.\u5c07queue.front != last_pos[x[queue.front]]\u7684\u5143\u7d20pop\u51fa\u4f86<br>8.\u82e5\u662fcount == K\u5247\u53d6\u4e00\u6b21\u6700\u5c0f\u9577\u5ea6<br>9.\u8f38\u51fa\u9577\u5ea6<br>\u88dc\u5145:<br>\u4ee5last_pos\u7d00\u9304\u6578\u5b57\u6700\u5f8c\u51fa\u73fe\u7684index\u53ef\u4ee5\u78ba\u5b9a\u4f4d\u65bcqueue\u88e1\u7684\u6578\u5b57\u662f\u5426\u91cd\u8907\uff0c\u56e0\u70baqueue\u88e1\u7684\u5c31\u662f\u6578\u5b57\u7684index in x\uff0c\u6240\u4ee5\u82e5\u662f\u8a72\u6578\u5b57last_pos\u4e0d\u7b49\u65bcqueue.front\u7684\u8a71\uff0c\u4ee3\u8868\u5f8c\u9762\u53c8\u8d70\u8a2a\u904e\u8a72\u6578\u5b57\uff0c\u5373\u91cd\u8907<\/p>\n\n\n\n<pre title=\"\u7a0b\u5f0f\u78bc\" class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">#include&nbsp;&lt;iostream&gt;\n#include&nbsp;&lt;vector&gt;\n#include&nbsp;&lt;queue&gt;\nusing&nbsp;namespace&nbsp;std;\nint&nbsp;main()&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;Case&nbsp;=&nbsp;1;\n&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;n;\n&nbsp;&nbsp;&nbsp;&nbsp;cin&nbsp;&gt;&gt;&nbsp;n;\n&nbsp;&nbsp;&nbsp;&nbsp;while(n--)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;n,m,k;\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cin&nbsp;&gt;&gt;&nbsp;n&nbsp;&gt;&gt;&nbsp;m&nbsp;&gt;&gt;&nbsp;k;\n\n<em>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\/\/\u521d\u59cb\u5316\u9663\u5217<\/em>\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;vector&lt;int&gt;&nbsp;x(n&nbsp;+&nbsp;1,0);\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x[1]&nbsp;=&nbsp;1;\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x[2]&nbsp;=&nbsp;2;\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x[3]&nbsp;=&nbsp;3;\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;i&nbsp;=&nbsp;4;&nbsp;i&nbsp;&lt;=&nbsp;n;&nbsp;i++)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x[i]&nbsp;=&nbsp;(x[i&nbsp;-&nbsp;1]&nbsp;+&nbsp;x[i&nbsp;-&nbsp;2]&nbsp;+&nbsp;x[i&nbsp;-&nbsp;3])&nbsp;%&nbsp;m&nbsp;+&nbsp;1;\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;vector&lt;int&gt;&nbsp;last_pos(k&nbsp;+&nbsp;1,0);\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;count&nbsp;=&nbsp;0;<em>\/\/\u7d00\u9304\u5df2\u51fa\u73fe\u76841~k\u7e3d\u6578\uff0c\u7b49\u65bck\u5373\u5168\u90e8\u51fa\u73fe<\/em>\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;queue&lt;int&gt;&nbsp;subarr;<em>\/\/\u653e\u5165\u5c0f\u65bck\u7684\u6578\u5b57\u4e4bindex<\/em>\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;minlen&nbsp;=&nbsp;1000001;\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;i&nbsp;=&nbsp;1;&nbsp;i&nbsp;&lt;=&nbsp;n;&nbsp;i++)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;cur&nbsp;=&nbsp;x[i];\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(cur&nbsp;&gt;=&nbsp;1&nbsp;&amp;&amp;&nbsp;cur&nbsp;&lt;=&nbsp;k)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;subarr.push(i);\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(last_pos[cur]&nbsp;==&nbsp;0)&nbsp;{<em>\/\/CHECK\u8a72\u6578\u5b57\u662f\u5426\u70ba\u7b2c\u4e00\u6b21\u51fa\u73fe<\/em>\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;count++;\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;last_pos[cur]&nbsp;=&nbsp;i;<em>\/\/RECORD&nbsp;LAST&nbsp;POSITION<\/em>\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while(subarr.front()&nbsp;!=&nbsp;last_pos[x[subarr.front()]])&nbsp;{<em>\/\/POP&nbsp;THE&nbsp;DUPLICATED&nbsp;NUMBER<\/em>\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;subarr.pop();\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(count&nbsp;==&nbsp;k)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;minlen&nbsp;=&nbsp;min(minlen,subarr.back()&nbsp;-&nbsp;subarr.front()&nbsp;+&nbsp;1);\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(minlen&nbsp;==&nbsp;1000001)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf(\"Case&nbsp;%d:&nbsp;sequence&nbsp;nai\\n\",Case++);\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf(\"Case&nbsp;%d:&nbsp;%d\\n\",Case++,minlen);\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\n&nbsp;&nbsp;&nbsp;&nbsp;}\n}<\/code><\/pre>\n\n\n\n<div class=\"wp-block-katex-display-block katex-eq\" data-katex-display=\"true\"><pre>\u6642\u9593\u8907\u96dc\u5ea6: O(N)<\/pre><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u672c\u4eba\u65bc\u8a72blog\u7684\u5168\u90e8\u6587\u7ae0\u8f49\u79fb\u81f3[UVA] 11536 Smallest Sub-Array &#8211;  [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[25],"tags":[26],"_links":{"self":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/315"}],"collection":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/comments?post=315"}],"version-history":[{"count":10,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/315\/revisions"}],"predecessor-version":[{"id":340,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/315\/revisions\/340"}],"wp:attachment":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/media?parent=315"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/categories?post=315"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/tags?post=315"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}